Browse thread
[Caml-list] Doubly-linked list
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2002-08-15 (09:19) |
From: | Anton E. Moscal <msk@m...> |
Subject: | Re: [Caml-list] Doubly-linked list |
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