Functionals for Lazy Lists

filterq: lazy filtering

let rec filterq p = function
  | Nil -> Nil
  | Cons (x, xf) ->
      if p x then
        Cons (x, fun () -> filterq p (xf ()))
      else
        filterq p (xf ())
(* val filterq : ('a -> bool) -> 'a seq -> 'a seq = <fun> *)

filterq demands elements from the sequence until it finds one satisfying p. It contains a force (xf()) not protected by a delay in the else branch: if no element satisfies the predicate within a finite prefix, filterq will evaluate the rest before producing any output.

Behaviour with infinite sequences

If the input sequence is infinite and contains no element satisfying p, then filterq runs forever without producing any output. This is a natural consequence: the function cannot know that no matching element exists without examining every element, of which there are infinitely many.

iterates: generalised from

let rec iterates f x =
  Cons (x, fun () -> iterates f (f x))
(* val iterates : ('a -> 'a) -> 'a -> 'a seq = <fun> *)

iterates f x generates the infinite sequence:

x, f(x), f(f(x)), f(f(f(x))), …

This generalises from: from k is equivalent to iterates (fun n -> n + 1) k.

Exercise: map analogue for sequences

A lazy map functional would apply a function to every element of a sequence on demand. The key is to delay the recursive call:

let rec mapq f = function
  | Nil -> Nil
  | Cons (x, xf) -> Cons (f x, fun () -> mapq f (xf ()))

The fun () -> around the recursive call ensures that the tail is computed only when forced by the consumer.