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 SAA30152; Tue, 13 Aug 2002 18:16:48 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA30071 for ; Tue, 13 Aug 2002 18:16:47 +0200 (MET DST) Received: from bastion.artisan.com (bastion.artisan.com [209.144.161.130]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g7DGGkL23630 for ; Tue, 13 Aug 2002 18:16:46 +0200 (MET DST) Received: from ypmaster.artisan.com (ypmaster [172.16.2.1]) by bastion.artisan.com (8.9.2/8.9.2) with ESMTP id JAA29012; Tue, 13 Aug 2002 09:16:42 -0700 (PDT) Received: from granite.artisan.com (granite [172.16.10.97]) by ypmaster.artisan.com (8.9.2/8.9.2-arti) with ESMTP id JAA27840; Tue, 13 Aug 2002 09:16:41 -0700 (PDT) Received: (from bpr@localhost) by granite.artisan.com (8.9.2/8.9.2) id JAA03630; Tue, 13 Aug 2002 09:16:41 -0700 (PDT) X-Authentication-Warning: granite.artisan.com: bpr set sender to bpr@artisan.com using -f From: Brian Rogoff MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Message-ID: <15705.12521.60353.709909@granite.artisan.com> Date: Tue, 13 Aug 2002 09:16:41 -0700 To: Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr Cc: caml-list@inria.fr Subject: Re: [Caml-list] Doubly-linked list References: <200208130759.DAA26086@dewberry.cc.columbia.edu> X-Mailer: VM 7.00 under Emacs 20.7.1 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Diego Olivier Fernandez Pons writes: > Oleg a =E9crit : >=20 > > P.S. BTW, one could have identical interfaces for a) resizable arra= ys, b)=20 > > doubly-linked lists and c) deques, the only difference being the ef= ficiency=20 > > of various operations. It could be convenient for a programmer, bec= ause final=20 > > data representation can be chosen after the program has been profil= ed and=20 > > without changing much code. Has anyone tackled this problem? >=20 > I will be soon releasing a data structure library (september) which > includes a port of EDiSon (GHC/hslibs/data/Edison in the GHC CVS), al= l > data structures that were in Okasaki's purely functional data > structures book and some more (weight balanced trees, cartesian trees= , > priority search queues, ...) I'm looking forward to seeing it. I get the impression that Edison uses= =20 (multi-parameter) type classes so it isn't clear that it will translate= =20 well. Oh yeah, I may as well add my biannual plea for some form of overloading in OCaml, which is somewhere in the top 3 of my wishlist.=20= Anyways, doubly linked lists are a textbook example of an imperative da= ta=20 structure, and, waddya know, a very good textbook (the Cousineau/Mauny = one which is owned by everyone on this list ;-) has this example pretty ear= ly in the section on imperative programming. Look here for the source=20 http://pauillac.inria.fr/cousineau-mauny/main.html but realize that you'll have to translate the source into OCaml. If I remember correctly, the doubly linked list looks something like=20 type 'a t =3D=20 { data : 'a;=20 mutable prev : 'a t;=20 mutable next : 'a t } let create e =3D let rec x =3D {data =3D e; prev =3D x; next =3D x} in = x etc.=20 which is very nice if you are used to trying such things in SML.=20 -- Brian ------------------- 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