listfunctional-programmingdictionaryocamllazy-evaluation

Ocaml List: Implement append and map functions


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!


Solution

  • 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).