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 LAA29741; Thu, 15 Aug 2002 11:19:17 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA29791 for caml-list@pauillac.inria.fr; Thu, 15 Aug 2002 11:19:16 +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 UAA00245 for ; Tue, 13 Aug 2002 20:22:51 +0200 (MET DST) Received: from gnome04.net.rol.ru (gnome04.net.rol.ru [194.67.1.185]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g7DIMnL27012 for ; Tue, 13 Aug 2002 20:22:50 +0200 (MET DST) Received: from ts1-a90.Spb.dial.rol.ru ([195.190.98.90]:39552 "HELO there" ident: "NO-IDENT-SERVICE[2]" whoson: "amoscal" smtp-auth: TLS-CIPHER: TLS-PEER: ) by gnome04.net.rol.ru with SMTP id ; Tue, 13 Aug 2002 22:22:48 +0400 Content-Type: text/plain; charset=US-ASCII From: "Anton E. Moscal" To: Oleg , "Anton Moscal" Subject: Re: [Caml-list] Doubly-linked list Date: Tue, 13 Aug 2002 22:23:20 +0400 X-Mailer: KMail [version 1.3.1] Cc: References: <012001c242db$ba4c9f90$2be213c3@youngkouzdra> <200208131611.MAA00208@dewberry.cc.columbia.edu> In-Reply-To: <200208131611.MAA00208@dewberry.cc.columbia.edu> MIME-Version: 1.0 Content-Transfer-Encoding: 7BIT Message-Id: <20020813182248Z4350324-9727+7354@gnome04.net.rol.ru> Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 13 Aug 2002 20:12, Oleg wrote: > > O> be purely functional? It's hard for me to think of an efficient > > O> purely functional doubly-linked list. > > > > For example: > > > > type 'a dll = 'a list (* before *) * 'a * 'a list (* next *) > > I don't think this is a doubly-linked list. In a doubly-linked listl, > _each_ element contains "references" to the next and previous elements. In > your dll type, there is only one such element. > > Anyways, in O'Reilly book (and a verion posted to the list about two years > ago), there is something similar to > > type 'a dlist = {mutable prev : 'a dlist option; > mutable next : 'a dlist option; > info : 'a} This isn't "purely functional" :) > > But I don't think it's very practically usable in its vanilla form. I > wouldn't use a doubly-linked list implementation unles it provided > O(1) push_back, push_front, back, front, length (?), insert_before, > insert_after, erase. insert_before, erase (AKA empty), length in my representation are straightforward. push_back, push_front etc are more complex, but probably - asymtotically O(1). Really, my solution is a variarion on theme of the purely functional queue which can be found in Okasaki (or surprisingly - in the Gries "Science of programming" :) ) Anton ------------------- 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