Ocaml List: Implement append and map functions

Question

I'm currently trying to extend a friend's OCaml program. It's a huge collection of functions needed for some data analysis.. Since I'm not really an OCaml crack I'm currently stuck on a (for me) strange List implementation:

type 'a cell = Nil
    | Cons of ('a * 'a llist)
and 'a llist = (unit -> 'a cell);;

I've figured out that this implements some sort of "lazy" list, but I have absolutely no idea how it really works. I need to implement an Append and a Map Function based on the above type. Has anybody got an idea how to do that?

Any help would really be appreciated!

Answer 1

let rec append l1 l2 = 
    match l1 () with
        Nil -> l2 | 
        (Cons (a, l)) -> fun () -> (Cons (a, append l l2));;

let rec map f l =
    fun () -> 
        match l () with
            Nil -> Nil | 
            (Cons (a, r)) -> fun () -> (Cons (f a, map f r));;

The basic idea of this implementation of lazy lists is that each computation is encapsulated in a function (the technical term is a closure) via fun () -> x. The expression x is then only evaluated when the function is applied to () (the unit value, which contains no information).

Answer 2

It might help to note that function closures are essentially equivalent to lazy values:

lazy n : 'a Lazy.t    <=>    (fun () -> n) : unit -> 'a
force x : 'a          <=>    x () : 'a

So the type 'a llist is equivalent to

type 'a llist = 'a cell Lazy.t

i.e., a lazy cell value.

A map implementation might make more sense in terms of the above definition

let rec map f lst =
  match force lst with
    | Nil -> lazy Nil
    | Cons (hd,tl) -> lazy (Cons (f hd, map f tl))

Translating that back into closures:

let rec map f lst =
  match lst () with
    | Nil -> (fun () -> Nil)
    | Cons (hd,tl) -> (fun () -> Cons (f hd, map f tl))

Similarly with append

let rec append a b =
  match force a with
    | Nil -> b
    | Cons (hd,tl) -> lazy (Cons (hd, append tl b))

becomes

let rec append a b =
  match a () with
    | Nil -> b
    | Cons (hd,tl) -> (fun () -> Cons (hd, append tl b))

I generally prefer to use the lazy syntax, since it makes it more clear what's going on.

Note, also, that a lazy suspension and a closure are not exactly equivalent. For example,

let x = lazy (print_endline "foo") in
  force x;
  force x

prints

foo

whereas

let x = fun () -> print_endline "foo" in
  x ();
  x ()

prints

foo
foo

The difference is that force computes the value of the expression exactly once.