Re: Imperative list operations

[John Prevost <prevost@maya.com>]

Steve Stevenson <steve@cs.clemson.edu> writes:

> 	I need a double-ended queue implementation. {...imperative...}

> 	I've tried all the naïve type declarations --- all of which
> don't seem to work.  I've tried the age old tricks. What am I not
> understanding? or doing right? I'm not fussy: tuples, records or
> objects are fine.

It'd help to know what you've tried.  The following work for me:

type 'a dlist_node =
  | Nil
  | Node of 'a dlist_node ref * 'a * 'a dlist_node ref

Or better:

type 'a dlist_node =
  { mutable dlist_prev : 'a dlist_node option;
            dlist_val  : 'a;
    mutable dlist_next : 'a dlist_node option }

Note that in the first case, you need to use value constructors, since:

type 'a dlist_node = 'a dlist_node option ref * 'a * 'a dlist_node option ref

is recursive, and O'Caml doesn't allow type aliases (as opposed to
union types or record types, which "create" new types) to be
recursive.

John.