Lazy Lists in OCaml

The unit type

The primitive type unit has exactly one value, written (). It may be regarded as a 0-tuple. Its uses include:

• Placeholder in data structures (e.g. a unit-valued dictionary represents a set)
• Argument to delay evaluation: fun () -> E
• Result of procedures that perform side effects

The lazy list type

type 'a seq =
  | Nil
  | Cons of 'a * (unit -> 'a seq)

A sequence is either empty (Nil) or a Cons cell containing a head value and a tail function of type unit -> 'a seq. The tail is not evaluated until the function is called - this is delayed evaluation, which is weaker than full lazy evaluation but sufficient for our purposes.

Key operations

let head (Cons (x, _)) = x

let tail (Cons (_, xf)) = xf ()

• head returns the first element immediately.
• tail forces evaluation by calling the tail function xf() with the unit argument (). The () serves as a placeholder - we need some argument to trigger evaluation, but no actual information is required.

Delaying evaluation

The expression fun () -> E delays evaluation of E: E is not computed until the function is called, even though the only possible argument is (). This is the key mechanism for implementing laziness in a strict language like OCaml.

The pattern

Every force must be enclosed within a delay for a function to remain lazy:

(* Correct - lazy *)
Cons (x, fun () -> ... xf () ...)

(* Risky - may force the whole sequence *)
... xf () ...

A force (xf()) not protected by a delay runs the risk of evaluating the entire sequence, defeating the purpose of laziness.

OCaml vs Haskell

Haskell uses lazy evaluation everywhere - even if-then-else can be a function and all lists are lazy. OCaml provides delayed evaluation through the unit -> 'a thunk pattern, which is a good compromise between performance and expressiveness. The result of forcing is not memoised in OCaml (unlike Haskell), so repeated forcing recomputes the value.