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

Answer 2

You can only build a cyclic immutable strict data structure of a shape that's determined at compile time. I'm not going to define or prove this formally, but intuitively speaking, once the data structure is created, its shape isn't going to change (because it's immutable). So you can't add to a cycle. And if you create any element of the cycle, you need to create all the other elements of the cycle at the same time, because you can't have any dangling pointer.

Ocaml can do what Haskell can do, but you do have to get the Lazy module involved! Unlike Haskell's, ML's data structures are strict unless otherwise specified. A lazy data structure has pieces of type 'a Lazy.t. (ML's typing is more precise than Haskell on that particular issue.) Lazy data structures allow cycles to be built by having provisionally-dangling pointers (whose linked values are automatically created when the pointer is first dereferenced).

type 'a lazy_dlist_value =
  | Dnil
  | Dnode of 'a lazy_dlist_value * 'a * 'a lazy_dlist_value
 and 'a lazy_dlist = 'a lazy_dlist_value Lazy.t

Another common way to have cyclic data structures is to use mutable nodes. (In fact, die-hard proponents of strict programming might see lazy data structures as a special case of mutable data structures that doesn't break referential transparency too much.)

type 'a mutable_dlist_value =
  | Dnil
  | Dnode of 'a mutable_dlist_value * 'a * 'a mutable_dlist_value
 and 'a mutable_dlist = 'a mutable_dlist_value ref

Cyclic data structures are mostly useful when they involve at least one mutable component, one function (closure), or sometimes modules. But there'd be no reason for the compiler to enforce that — cyclic strict immutable first-order data structures are just a special case which can occasionally be useful.

Answer 3

type 'a dlist = Dnil | Dnode of 'a dlist Lazy.t * 'a * 'a dlist Lazy.t
let rec of_list list = match list with
    [] -> Dnil
    | x :: [] ->
        let rec single () = Dnode (lazy (single ()), x, lazy (single ()))
        in single ()
    | x :: y -> Dnode (
        lazy (
            of_list (match List.rev list with
                [] | _ :: [] -> assert false
                | x :: y -> x :: List.rev y
            )
        ),
        x,
        lazy (
            of_list (match list with
                [] | _ :: [] -> assert false
                | x :: y -> y @ x :: []
            )
        )
    )
let middle dlist = match dlist with
    Dnil -> raise (Failure "middle")
    | Dnode (_, x, _) -> x
let left dlist = match dlist with
    Dnil -> raise (Failure "left")
    | Dnode (x, _, _) -> Lazy.force x
let right dlist = match dlist with
    Dnil -> raise (Failure "right")
    | Dnode (_, _, x) -> Lazy.force x