# Batteries.LazyList.lazy_fold_right?

`Batteries.LazyList.lazy_fold_right` has what seems like a strange type signature. I have two sets of questions:

1. What’s the easiest way to use `lazy_fold_right`? What’s the easiest way to construct and deconstruct the `Lazy.t` things that its combining function requires?

2. Why doesn’t `lazy_fold_right` have a normal `fold_right` signature? Why does one have to go through extra work to compute a fold lazily? Shouldn’t that extra work be done by the `fold_right` function for us?

(In the example below, I use `lazy_fold_right` to compute a small sum, which is kind of silly. I actually want to use it to transform a lazy list into a different lazy list in which each element depends on the previous element.)

Example sequences:

``````# open Batteries;;
# let num_list = List.range 0 `To 10;;
val num_list : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
# let num_lazylist = LazyList.seq 0 ((+) 1) ((>=) 10);;
val num_lazylist : int LazyList.t = <lazy>
# LazyList.to_list num_lazylist;;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
``````

Here’s how `List.fold_right` and `LazyList.eager_fold_right` work:

``````# List.fold_right;;
- : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
# List.fold_right (+) num_list 0;;
- : int = 55
# LazyList.eager_fold_right;;
- : ('a -> 'b -> 'b) -> 'a LazyList.t -> 'b -> 'b = <fun>
``````

That signature is what I would expect, and the function works as expected:

``````# LazyList.eager_fold_right (+) num_lazylist 0;;
- : int = 55
``````

Now for lazy folding:

``````# LazyList.lazy_fold_right;;
- : ('a -> 'b lazy_t -> 'b) -> 'a LazyList.t -> 'b lazy_t -> 'b lazy_t = <fun>
``````

That signature looks odd. What’s `lazy_t`? (From other investigations I know that it’s also `Lazy.t` from the standard library). Let’s see what happens:

``````# LazyList.lazy_fold_right (+) num_lazylist 0;;
Error: This expression has type int -> int -> int but an expression was expected of type int -> 'a lazy_t -> 'a
Type int is not compatible with type 'a lazy_t
``````

I also have a long series of failed experiments trying to pass a combining function that will accept and return `lazy_t` or `Lazy.t`. I can add them here if anyone wants to see what I tried, but they are a complicated mess and they all produce type or syntax errors.

`'a lazy_t` indicates that the value inside might not be fully evaluated (e.g. an infinite list). You can use the `Lazy.force : 'a lazy_t -> 'a` function to fully evaluate it (for a LazyList, it will only evaluate the head if one exists).

In your case, you want a function of type signature `'a -> 'a lazy_t -> 'a` where '`a = int`.

``````utop # let lazy_plus a b = a + Lazy.force b;;
val lazy_plus : int -> int lazy_t -> int = <fun>
utop # LazyList.lazy_fold_right lazy_plus num_lazylist 0;;
Error: This expression has type int but an expression was expected of type
int lazy_t
``````

Oops, the last argument should be a lazy value.

``````utop # LazyList.lazy_fold_right;;
- : ('a -> 'b lazy_t -> 'b) -> 'a LazyList.t -> 'b lazy_t -> 'b lazy_t = <fun>
``````

You can create lazy values from ordinary values using the `lazy` keyword.

``````utop # let x = LazyList.lazy_fold_right lazy_plus num_lazylist (lazy 0);;
val x : int lazy_t = <lazy>
``````

Now you have a lazy integer as a result, which you can evaluation using `Lazy.force`.

``````utop # Lazy.force x;;
- : int = 55
``````

W.r.t. `eager_fold_right`/`fold_right` (they’re identical apart from the order of the arguments), they will not work if you try using them with infinite lists.