Infinite Sequences

Generating infinite sequences: from

let rec from k = Cons (k, fun () -> from (k + 1))
(* val from : int -> int seq = <fun> *)

from k produces the infinite sequence k, k+1, k+2, … . Execution terminates because the recursive call from (k+1) is enclosed within fun () -> .... Without this delay, the recursion would be unbounded and the function would never return.

Interactive exploration

let it = from 1
(* val it : int seq = Cons (1, <fun>) *)

let it = tail it
(* val it : int seq = Cons (2, <fun>) *)

let it = tail it
(* val it : int seq = Cons (3, <fun>) *)

OCaml displays the tail of a sequence as <fun>. Each call to tail generates the next element.

Consuming a sequence: get

let rec get n s =
  match n, s with
  | 0, _            -> []
  | n, Nil          -> []
  | n, Cons (x, xf) -> x :: get (n - 1) (xf ())
(* val get : int -> 'a seq -> 'a list = <fun> *)

get n s extracts the first n elements as an ordinary list. The call xf() forces evaluation of the next element. If n is negative, it takes all elements (terminating only for finite sequences).

Evaluation trace

Consider get(2, from 6):

get(2, from 6)
=> get(2, Cons(6, fun () -> from (6+1)))
=> 6 :: get(1, from (6+1))
=> 6 :: get(1, Cons(7, fun () -> from (7+1)))
=> 6 :: 7 :: get(0, Cons(8, fun () -> from (8+1)))
=> 6 :: 7 :: []
=> [6; 7]

Note: three elements are computed (6, 7, and 8), even though only two were requested. Our implementation is slightly too eager - the tail of the last Cons is constructed before get checks that n = 0. A more complex type declaration could avoid this. In a truly lazy language like Haskell, only the demanded elements would be computed.