Re: Imperative list operations

From: Jerome Vouillon (Jerome.Vouillon@inria.fr)
Date: Wed Sep 15 1999 - 14:35:24 MET DST


Date: Wed, 15 Sep 1999 14:35:24 +0200
From: Jerome Vouillon <Jerome.Vouillon@inria.fr>
To: Steve Stevenson <steve@cs.clemson.edu>, caml-list@inria.fr
Subject: Re: Imperative list operations
In-Reply-To: <14302.41638.913957.615588@merlin.cs.clemson.edu>; from Steve Stevenson on Tue, Sep 14, 1999 at 03:36:18PM -0400

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



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:25 MET