We can use encapsulation within functions to delay evaluation in OCaml:

Now given

let rec next_int n = (n, Promise (fun() -> next_int (n + 1)));;
let naturals = Promise (fun() -> next_int (1));;

we have

head naturals;;                                     ⇒ 1
head (rest naturals);;                          ⇒ 2
head (rest (rest naturals));;                ⇒ 3
...
The delayed list naturals is effectively of unlimited length. It will be computed out only as far as actually needed. If a value is needed more than once, however, it will be recomputed every time. Show how to use pointers and assignment (Example 8.42) to memoize the values of a delayed_list, so that elements are computed only once.

Transcribed Image Text:

type 'a delayed_list Pair of 'a * 'a delayed_list | Promise of (unit -> 'a * 'a delayed list);; let head = function | Pair (h, r) -> h | Promise (f) -> let (a, b) = f() in a; ; let rest = function | Pair (h, r) -> r | Promise (f) -> let (a, b) = f() in b; ; %3D