Creating a doubly linked list from a list in OCaml

Question

I am often told that using the Lazy module in OCaml, one can do everything you can do in a lazy language such as Haskell. To test this claim, I'm trying to write a function that converts a regular list into a static doubly linked list in ocaml.

type 'a dlist = Dnil | Dnode of 'a dlist * 'a * 'a dlist

Given this type I can create several static doubly linked lists by hand:

let rec l1 = Dnode (Dnil,1,l2)
    and l2 = Dnode   (l1,2,l3)
    and l3 = Dnode   (l2,3,Dnil)

but I'd like to write a function of type 'a list -> 'a dlist that given any list builds a static doubly linked list in OCaml. For example given [1;2;3] it should output something equivalent to l1 above.

The algorithm is pretty straightforward to write in Haskell:

data DList a = Dnil | Dnode (DList a) a (DList a)

toDList :: [a] -> DList a
toDList l = go Dnil l
 where
  go _ [] = Dnil
  go h (x:xs) = let r = Dnode h x (go r xs) in r

but I haven't been able to figure out where to place calls to lazy to get this to compile in OCaml.

Answer 1

If you build your linked list in right-to-left order (as for normal lists), then the left element of every node will only be built after that node itself is built. You need to represent this by making the left element lazy, which means "this value will be constructed later" :

type 'a dlist = 
  | Dnil
  | Dnode of 'a dlist Lazy.t * 'a * 'a dlist

Once you have this, construct every node as a lazy value using a recursive definition which passes the lazy (still unconstructed) node to the function call that builds the next node (so that it has access to the previous node). It's actually simpler than it looks :

let dlist_of_list list = 
  let rec aux prev = function
    | [] -> Dnil
    | h :: t -> let rec node = lazy (Dnode (prev, h, aux node t)) in 
                Lazy.force node
  in
  aux (Lazy.lazy_from_val Dnil) list