Re: Imperative list operations

[Jerome Vouillon <Jerome.Vouillon@inria.fr>]

On Tue, Sep 14, 1999 at 03:36:18PM -0400, Steve Stevenson wrote:
> 	I need a double-ended queue implementation. The lists 
> can get very long, so I would like to use imperative operations to
> change the links.

There are some very nice and quite efficient purely functional
implementations of double-ended queues. I suggest you to have a look
at Chris Okasaki's work on http://www.cs.columbia.edu/~cdo/papers.html
(in particular, "Simple Confluently Persistent Catenable Lists",
"Catenable Double-Ended Queues" and "Simple and Efficient Purely
Functional Queues and Deques").

> 	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?

It is hard to guess without knowing what you have done...

You can use the following type definition :
    type 'a node =
       { mutable prev : 'a list; mutable next : 'a list; value : 'a }
    and 'a list = 'a node option;;
    type 'a dequeue = { mutable head : 'a list; mutable tail : 'a list}
A double-ended queue has a pointer to the head of the list and a
pointer to its tail. A list can either be empty (None) or contain a
sequence of nodes. A node holds a pointer to the nodes that precedes
it and a pointer to the nodes that follows it.

Ther is some space overhead in using option types. So, you could also
use a circular list. The type definition would be :
    type 'a node =
      { mutable prev : 'a node; mutable next : 'a node; val : 'a }
    type 'a dequeue = 'a node option ref
A double-ended queue is either empty (None) or point to the head of
the circular list. Each node has a pointer to the previous node and
the next node in the circular list.
Insertion and removal looks something like that :
  let insert_front d v =
    match !d with
      None ->
        let rec node = { prev = node; next = node; value = v } in
        d := Some node
    | Some n' ->
        let n = { prev = n'.prev; next = n'; value = v } in
        n'.prev.next <- n; n'.prev <- n;
        d := Some n;;
  let remove_front d =
    match !d with
      None ->
        raise Not_found
    | Some n when n.next == n ->
        d := None;
        n.value
    | Some n ->
        n.next.prev <- n.prev; n.prev.next <- n.next;
        d := Some n.next;
        n.value;;

Regards,

-- Jérôme