Ocaml List: Implement append and map functions
-
08-07-2019 - |
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!
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).
OTHER TIPS
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.
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.