Re: [Ocaml-lib-devel] Dllist

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

On Fri, 27 May 2005, Christophe TROESTLER wrote:

> On Thu, 26 May 2005, Brian Hurt <bh...@sp...> wrote:
>>
>> On Wed, 25 May 2005, Christophe TROESTLER wrote:
>>
>>> Hi,
>>>
>>> Is there a good reason (aside from implementation easiness) not to
>>> allow Dllist to be empty?  IMHO, empty lists are very useful and it is
>>> rather an hindrance that Dllists cannot be.
>>
>> My original implementation did allow for empty lists, but it got
>> overridden.
>
> Where?  The CVS version does not seem to allow it.  As an example,
> consider:
>
> # let l = create 1 in
>    demote l;
>    length l;;
> - : int = 1
>
> (hum).   How do you create an empty list?

If I recall correctly, the original implementation of dllist I submitted 
way back when worked like this:

type 'a node_t = {
     data: 'a;
     mutable next: 'a node_t;
     mutable prev: 'a node_t;
};;

type 'a t = {
     mutable head: 'a node_t option;
     mutable tail: 'a node_t option;
};;

let empty () = { head = None; tail = None };;

let prepend x lst =
     let rec newnode = { data = x; next = newnode; prev = newnode } in
     match lst.head with
         | Some(node) ->
              newnode.next <- node;
              node.prev <- newnode;
              lst.head <- Some(newnode)
         | None ->
             let opt = Some(newnode) in
             lst.tail <- opt;
             lst.head <- opt
;;

Which allows for the obvious empty list representation.  It got overrulled 
in an attempt to save a couple of clock of cycles and maybe a few bytes. 
Having fought this battle before, at length, and lost, I just said "yeah, 
sure, whatever".

Brian