Re: [Ocaml-lib-devel] Dllist

[Brian H. <bh...@sp...>]

On Sun, 29 May 2005, John Skaller wrote:

> Well my view is that a *base* library provides simple
> efficient things -- it is oriented to the computer NOT the user.

This is where you and I part company.  Computer cycles are cheap compared 
to human cycles.

> The problem with doing that is that you can't so easily
> chop bits of the list up, or splice bits of a list together.

Yep.  This is a problem with imperitive data structures.

>
> For example, consider two lists A and B, and you join them
> to create a list C. What happens to A and B?

A and B are now invalid lists.  Unless A is C.

Note that you can leave A and B in valid states.  Consider my example 
implementation I posted earlier, I couple implement the O(1) append like 
this:

let append a b =
     match a.tail, b.head with
         | None, _ ->
             a.head <- b.head;
             a.tail <- b.tail;
             b.head <- None;
             b.tail <- None;
             ()
         | _, None -> ()
         | Some(x), Some(y) ->
             x.next <- y;
             y.prev <- x;
             a.tail <- b.tail;
             b.head <- None;
             b.tail <- None;
             ()
;;

Conceptually, all the elements of B are removed from it an appended to A.

Yes, it's a destructive operation.  So?  Welcome to the imperitive world.

Brian