Re: [Caml-list] Doubly-linked list

["Anton E. Moscal" <msk@mail.tepkom.ru>]

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