ocaml-batteries-team/batteries-included — pull request #407 by gasche (2013-07-09 10:01:56+00:00)
Title: LazyList: new lazy_fold_right function

It is not entirely clear what is the "right" interface for a *lazy*
fold_right function. It cannot be the same interface as an eager
fold_right, as the typing of [fold_right] doesn't allow a lazy
traversal.

The current interface is:

val lazy_fold_right :
('a -> 'b Lazy.t -> 'b) -> 'a t -> 'b Lazy.t -> 'b Lazy.t
(**Lazy fold_right
[lazy_fold_right f (Cons (a0, Cons (a1, Cons (a2, nil)))) b] is
[lazy (f a0 (lazy (f a1 (lazy (f a2 b)))))].

Forcing the result of [lazy_fold_right] forces the first element of
the list; the rest is forced only if/when the function [f] forces
its accumulator argument.
*)

Note that:

(1) The return value of the folding function [f] has type ['b], while
it could be ['b Lazy.t]; those are in fact equivalent: when the
function [f] forces its accumulator argument (of type ['b
Lazy.t]), the tail of the list is forced, and if it is a [Cons]
the function [f] is called and must produce a ['b] (as we are
forcing a ['b Lazy.t]); if [f] returned a lazy value, we would
have to force it immediately. And this is the only call site of
[f]. Making its return type ['b] instead of ['b Lazy.t] therefore
faithfully represents what happens in practice (no computation
is delayed), and allow for a slightly more efficient code
(as opposed to immediately forcing [f]'s result) in case the user
indeed wants to return a concrete value directly, without any
forcing.

(2) The initial accumulator value (the last argument) has type
['b Lazy.t] instead of ['b]. This makes sense because lazyness can
be introduced here: this value only needs to be forced if/when
[fold_right] reaches the end of the input list (which does not
always happen). Asking the user (through a type ['b]) to have the
forced value at hand before calling the function would therefore
reduce expressiveness.