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.

Answer 3

Yes, the lists can be infinite. The code given in the other answers will append to the end of an infinite list, but there's no program you can write than can observe what is appended following an infinite list.