From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA02781; Mon, 19 Aug 2002 12:41:27 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA02732 for ; Mon, 19 Aug 2002 12:41:26 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g7JAfQD01402 for ; Mon, 19 Aug 2002 12:41:26 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.5/jtpda-5.4) with ESMTP id g7JAfNjR071737 ; Mon, 19 Aug 2002 12:41:23 +0200 (CEST) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id MAA29954 ; Mon, 19 Aug 2002 12:39:38 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with SMTP id MAA43236 ; Mon, 19 Aug 2002 12:38:09 +0200 Date: Mon, 19 Aug 2002 12:38:08 +0200 (DST) From: Diego Olivier Fernandez Pons To: Brian Rogoff cc: caml-list@inria.fr Subject: Re: [Caml-list] Doubly-linked list In-Reply-To: <15706.31385.247539.595347@granite.artisan.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Antivirus: scanned by sophie at shiva.jussieu.fr Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Brian Rogoff a =E9crit : > With OCaml 3.05 and above, you'll be able to use polymorphic methods to= =20 > get non-uniform recursion. This issue has come up a lot on the list=20 > (see the archives) over the years and several proposals were made for=20 > adding this capability to the language. I don't know if adding this=20 > feature is a priority for the developers; it isn't clear that the data > structures in Okasaki's book constitute a strong enough argument for=20 > adding it.=20 Non-uniform recursion allows you to capture structure invariants in your type, which means that the correction of the algorithms will not be proved by the programmer but by the type-checker.=20 I think it is a big improvment. Chris Okasaki's data structure may not be a strong enough argument, but more complicated data structures are being studied. You can find some (simple) examples in a paper by Ralf Hinze "Manufacturing data types", namely braun trees, 2-3 trees, matrices=20 Concerning double linked lists, for the moment I am working on things I think are more important. Diego Olivier ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners