Laziness, Memoization & Infinite Structures

32.1 lazy and Lazy.force

let expensive = lazy (print_endline "computing"; 42)
let a = Lazy.force expensive    (* prints "computing" *)
let b = Lazy.force expensive    (* cached: no print *)

match expensive with lazy v -> v     (* lazy patterns *)
Lazy.is_val, Lazy.from_val, Lazy.map

32.2 Lazy streams

type 'a stream = Cons of 'a * 'a stream Lazy.t

let rec from n = Cons (n, lazy (from (n + 1)))
let rec take n (Cons (x, rest)) = if n = 0 then [] else x :: take (n - 1) (Lazy.force rest)

let rec sieve (Cons (p, rest)) =
  let rec filter (Cons (x, r)) =
    if x mod p = 0 then filter (Lazy.force r) else Cons (x, lazy (filter (Lazy.force r))) in
  Cons (p, lazy (sieve (filter (Lazy.force rest))))

let primes = sieve (from 2)
let first10 = take 10 primes

32.3 Memoization

let memoize f =
  let cache = Hashtbl.create 16 in
  fun x -> match Hashtbl.find_opt cache x with
    | Some v -> v
    | None -> let v = f x in Hashtbl.add cache x v; v

(* Memoizing a recursive function: open recursion *)
let memo_rec f =
  let cache = Hashtbl.create 16 in
  let rec g x = match Hashtbl.find_opt cache x with
    | Some v -> v
    | None -> let v = f g x in Hashtbl.add cache x v; v in
  g

let fib = memo_rec (fun self n -> if n < 2 then n else self (n - 1) + self (n - 2))
let big = fib 90

32.4 Fixed-point combinator

let rec fix f x = f (fix f) x
let fact = fix (fun self n -> if n = 0 then 1 else n * self (n - 1))