Re: simulation of doubly linked lists in OCaml?

["Dennis (Gang) Chen" <Dennis.G.Chen@motorola.com>]

Jan Brosius wrote:

> Hi, I wonder if it is possible to simulate by datatype constructors a doubly linked list
> in OCaml/ I read the english version about pointers in Ocaml, interesting but it is not
> cleat for me how to simulate a doubly linkedlist. Friendly Jan Brosius

Here is my code for doubly linked list.

type 'a tp_dlist =  Nil | Cell of 'a * 'a tp_dlist ref * 'a tp_dlist ref;;

let dlist_create () =  ref Nil;;

let rec dlist_member x rf_list =
  match !rf_list with
    Nil               -> false
  | Cell ( y, rf_left, rf_right ) ->
     if y = x then true else dlist_member x rf_right;;

(* insert a cell containing x to the front of the double list pointed by rf_list*)
let dlist_insert x rf_list =
   let new_tail = !rf_list in
       rf_list := Cell (x, ref Nil, ref new_tail);;

(* delete the first cell containing x from the double linked list pointed by rf_list *)
let rec dlist_delete x rf_list =
   match !rf_list with
        Nil  -> ()
      | Cell (y, rf_left, rf_right) ->
   if x = y then begin
             rf_list := !rf_right;
             match !rf_right with
                  Nil ->  ()
               |  Cell (z, rf_rleft , rf_rright) ->
                    rf_rleft := !rf_left
          end
          else dlist_delete x rf_right;;

let dlist_print rf_list =
 let rec dlist_pr rf_lst =
  match !rf_lst with
    Nil            ->  print_string " ]"; print_newline ()
  | Cell (y, rf_left, rf_right) ->
          print_int y; print_string "; "; dlist_pr rf_right
in print_string "[ "; dlist_pr rf_list;;

(* The following functiona are used to test *)
(* create a double linked list containing n+1, n, ..., 1 *)
let create_dlist n =
   let rf_inilist = ref Nil in
   let rec create rf_list i =
       if i>n then ()
       else begin  dlist_insert (i+1) rf_list; create rf_list (i+1) end
   in create rf_inilist 0; rf_inilist;;


(* Test results:

# let d1 = create_dlist 5;;
val d1 : int tp_dlist ref =
  {contents=
    Cell
     (6, {contents=Nil},
      {contents=
        Cell
         (5, {contents=Nil},
          {contents=
            Cell
             (4, {contents=Nil},
              {contents=
                Cell
                 (3, {contents=Nil},
                  {contents=
                    Cell
                     (2, {contents=Nil},
                      {contents=Cell (1, {contents=Nil}, {contents=Nil})})})})})})}
# dlist_print d1;;
[ 6; 5; 4; 3; 2; 1;  ]
- : unit = ()
# dlist_delete 4 d1;;
- : unit = ()
# dlist_print d1;;
[ 6; 5; 3; 2; 1;  ]
- : unit = ()
# dlist_delete 7 d1;;
- : unit = ()
# dlist_print d1;;
[ 6; 5; 3; 2; 1;  ]
- : unit = ()
*)

By the way,
I've done some  tests on list and set operations. I've not attached the codes
here because not all programs are of good quality and I have not got time to carefully
check if all results are reliable. Besides, attaching codes here might make
the mail too big. Anyone who is interested in these codes can contact me directly.
Verifying the results and improving the codes are welcome.

The experimental result show that the deletion operation for functional list
is quite slow in the worst case.
I compile the native code:

ocamlopt listTest.ml -o mlListTest

Then call
dchen% .time /mlListTest 100000 50000 200 2

It creates a list of size 100000 and repeat 200 times
for inserting an element in the front of the list and deleting an element
in the last position. The second argument 50000 is useless for this test.
On my machine, it tooks 59:53 user time to finish.
59.53u 0.09s 1:32.29 64.6%

For a linked list built in C, I have
g++ pointer.cpp -o pointer
time ./pointer 100000 50000 200 2
3.80u 0.04s 0:06.81 56.3%

Mutable list in ocaml works much faster than functional list, although still
somewhat slower than C code:

ocamlopt mlistTest.ml -o mlistTest
time ./mlistTest 100000 50000 200 2
6.62u 0.05s 0:09.56 69.7%

The performance would be improved if using the implementation proposed
in ocaml FAQ.

To my surprise, the ocaml ordered set library is faster than STL set in all three
operations that I tested:  set creation, membership AND deletion.

ocamlopt setTest.ml -o setTest

The deletion is surprisingly fast:
time ./setTest 100000 50000 200000 2
5.41u 0.06s 0:09.00 60.7%

It adds the number 50000 into the balanced tree of size 100000, then deletes it.
The operation repeats for 200000 times.

This is even faster than STL set:
g++ stlSetTest.cpp -o stlSetTest
time ./stlSetTest 100000 50000 200000 2
8.83u 0.02s 0:14.14 62.5%

The ocaml set is functional and each deletion needs to rebuid a subtree.
Although this subtree might be significantly smaller than the whole tree,
but such a good performance is still amazing.
Here is the code to test the deletion:

let rec deletion_test ele cnt set =
   if cnt > 0 then
      deletion_test ele (cnt-1) (IntSet.remove ele (IntSet.add ele set))
   else ();;


Cheers.

--
Dennis Gang CHEN    Senior Software Engineer
Motorola Australia Software Centre, Electronic Design Automation
2 Second Avenue, Mawson Lakes, SA 5095, Australia
phone: +61 8 8203 3560,  mailto: Dennis.G.Chen@motorola.com