Imperative list operations

Imperative list operations

[Steve Stevenson]

[Sorry, English only.]

Good afternoon.
	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.

	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.

Best regards,

steve
-----
Steve (really "D. E.") Stevenson           Assoc Prof
Department of Computer Science, Clemson,   (864)656-5880.mabell
Support V&V mailing list: ivandv@cs.clemson.edu
	

Re: Imperative list operations

[Jerome Vouillon]

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

Re: Imperative list operations

[Steve Stevenson]

Jérôme:

I've been programming for 35 years. It always amazes me how little I
understand. Thanks.

Best regards,

steve
-----
Steve (really "D. E.") Stevenson           Assoc Prof
Department of Computer Science, Clemson,   (864)656-5880.mabell
Support V&V mailing list: ivandv@cs.clemson.edu

Re: Imperative list operations

[John Prevost]

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.

Re: Imperative list operations

[Stefan Monnier]

>>>>> "Steve" == Steve Stevenson <steve@cs.clemson.edu> writes:
> 	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.

Since my O'Caml is very approximate, I'll answer with a non-answer:
have you tried a purely functional (but asymptotically efficient)
deque ?  Those don't suffer from the length of the queue.

Chris Okasaki has an interesting set of such purely functional data-structures,
with sample code in SML (and/or Haskell) which should be easy to translate to
O'Caml.  Check out, for example http://www.cs.columbia.edu/~cdo/jfp95/


	Stefan

Re: Imperative list operations

[Christophe Raffalli]

Try this:

(************** dlist.mli ***********************)
type 'a dlist

val empty : unit -> 'a dlist
val move_left : 'a dlist -> 'a dlist
val move_right : 'a dlist -> 'a dlist
val get_content : 'a dlist -> 'a
val is_left_end : 'a dlist -> bool
val is_right_end : 'a dlist -> bool
val is_not_end : 'a dlist -> bool
val is_empty : 'a dlist -> bool
val insert_right : 'a -> 'a dlist -> unit


(************** dlist.ml ************************)


type 'a dlist =
  | Cell of 'a cell
  | End_Left of 'a end_left
  | End_Right of 'a end_right

and 'a cell = { 
    dlist_cell : 'a; 
    mutable dlist_left : 'a dlist;
    mutable dlist_right : 'a dlist 
  }

and 'a end_left = {
    mutable back_right : 'a dlist;
  } 

and 'a end_right = {
    mutable back_left : 'a dlist;
  } 

let empty () =
  let rec l = 
    End_Left { back_right = End_Right { back_left = l }}
  in l

let move_left l =
  match l with
  | End_Left sr ->
      raise (Invalid_argument "move_left")
  | End_Right sl ->
      sl.back_left
  | Cell s ->
      s.dlist_left

let move_right l =
  match l with
  | End_Left sr ->
      sr.back_right
  | End_Right sl ->
      raise (Invalid_argument "move_right")
  | Cell s ->
      s.dlist_right

let get_content l =
  match l with
  | End_Left sr ->
      raise (Invalid_argument "get_content")
  | End_Right sl ->
      raise (Invalid_argument "get_content")
  | Cell s ->
      s.dlist_cell

let is_left_end = function
    End_Left _ -> true
  | _ -> false

let is_right_end = function
    End_Right _ -> true
  | _ -> false

let is_not_end = function
    Cell _ -> true
  | _ -> false

let is_empty = function
    End_Left sr -> is_right_end sr.back_right
  | End_Right sl -> is_left_end sl.back_left
  | _ -> false

let insert_right a l = 
  let li, lr = match l with
    End_Left sr ->
      let lr = sr.back_right in
      let li = Cell {
	dlist_cell = a;
	dlist_left = l;
	dlist_right = lr;
      }	in
      sr.back_right <- li;
      li, lr
  | End_Right sl ->
      raise (Invalid_argument "insert_left")
  | Cell s ->
      let lr = s.dlist_right in
      let li = Cell {
	dlist_cell = a;
	dlist_left = l;
	dlist_right = lr;
      }	in
      s.dlist_right <- li;
      li, lr
  in
  match lr with
    End_Right sl -> sl.back_left <- li
  | Cell s -> s.dlist_left <- li
  | End_Left sr -> raise (Failure "impossible in insert_left")

let insert_left a l = 
  let li, ll = match l with
    End_Right sl ->
      let ll = sl.back_left in
      let li = Cell {
	dlist_cell = a;
	dlist_left = ll;
	dlist_right = l;
      }	in
      sl.back_left <- li;
      li, ll
  | End_Left sr ->
      raise (Invalid_argument "insert_right")
  | Cell s ->
      let ll = s.dlist_left in
      let li = Cell {
	dlist_cell = a;
	dlist_left = ll;
	dlist_right = l;
      }	in
      s.dlist_left <- li;
      li, ll
  in
  match ll with
    End_Left sr -> sr.back_right <- li
  | Cell s -> s.dlist_right <- li
  | End_Right sl -> raise (Failure "impossible in insert_left")

(*
  test

let x = empty ();;
insert_right 2 x;;
let x' = move_right x;;
insert_right 3 x';;
insert_left 1 x';;
get_content (move_left x');;
get_content (move_right x');;
insert_right 4 x';;
insert_left 0 x';;
get_content (move_left x');;
get_content (move_right x');;
get_content (move_left (move_left x'));;
get_content (move_right (move_right x'));;
*)

Re: Imperative list operations

[Markus Mottl]

> Chris Okasaki has an interesting set of such purely functional data-structures,
> with sample code in SML (and/or Haskell) which should be easy to translate to
> O'Caml.  Check out, for example http://www.cs.columbia.edu/~cdo/jfp95/

If you do not want to translate it to OCaml yourself, you may
also take a look at my translation, which you can find at:
http://miss.wu-wien.ac.at/~mottl/ocaml_sources/intro.html

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl