Batteries.LazyList.lazy_fold_right?

Learning
,
1

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.

2

'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.

3

Thanks @theindigamer. Still thinking about your answer.