Re: [Caml-list] Doubly-linked list

[Oleg <oleg_inconnu@myrealbox.com>]

On Tuesday 13 August 2002 11:11 am, Anton Moscal wrote:
> Hello, Oleg!
> You wrote to "Diego Olivier Fernandez Pons"
> <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr> on Tue, 13 Aug 2002
> 10:30:59 -0400:
>
>  O> Will it include imperative doubly-linked list or are all data types
>  O> going to
>  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}

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.

Maybe I'll write it in the next few days. What kind of bothers me is the need 
to have iterators (a la STL) as helper types.

Cheers
Oleg

> let ins_after elem (bef, cur, aft) = (cur::bef, elem, aft)
> let next = function (bef, cur, (cur'::aft)) -> Some ((cur::bef), cur', aft)
>
> | _ -> None
>
> let prev = function ((cur'::bef), cur, aft) -> Some (bef, cur', (cur::aft))
>
> | _ -> None
>
> ...
-------------------
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