Add lazy fold to Sequence

Libraries
1

Sequence.fold causes the evaluation of the whole sequence, which makes it useless with infinite sequences. It would be great to have a lazy fold.

I have implemented my own structure with lazy fold, which allows writing:

fun <A> Stream<A>.copy(): Stream<A> =
    this.foldRight({this.head()?.let{Stream.cons(it)} ?: Stream.empty()}, 
                        {a -> {sa: () -> Stream<A> -> Stream.cons({a}, sa)}})
println(Stream.from(0).copy().take(10).toList())

This prints:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, NIL]

Trying to do the same with Sequence.fold will not terminate because fold is not lazy. Of course, having lazy fold to implement copy may seems of little use, but this is just for demonstration. Lazy fold would allow defining scan functions operating on infinite sequence.

2

scan function is something we consider is good to have: https://youtrack.jetbrains.com/issue/KT-7657

Currently it requires specification to be written. You can contribute to that process, by authoring and submitting KEEP request for the standard library enhancement: KEEP/TEMPLATE.md at master · Kotlin/KEEP · GitHub

1 Like
3

This was not what I meant. If I need a scan function, I would implement it like this:

fun <A, B> Sequence<A>.scanLeft(f: (B, A) -> B, z: B): Sequence<B> = generate<B> {
  var acc = z
  for (a in this@scanLeft) {
    acc = f(acc, a)
    yield(acc)
  }
}

But this is not what I need. It was only an example. What I would need is a way to abstract what is common in many problems about collection such as mapping, filtering, concatenating, scanning, etc. And this abstraction is folding. So lazy collections needs lazy folding.

4

Could you elaborate how lazy fold differs from the proposed scan function?

1 Like
5

Not sure to understand what you mean. Lazy fold and scan are two very different things. Scan can be implemented through a fold, but a fold may be used to implement many other functions. For example, a fold may be used to make a copy of a collection. If you apply a function to each element while making the copy, you have just implemented map (or flatMap) through a fold.

The only problem is that the fold, if applied to a lazy collection, has to be a lazy fold. Otherwise, it would evaluate the collection.

6

Ok, I see, you need something like this?

fun <T, A> Sequence<T>.foldRight(initial: A, f: (T, () -> A) -> A): A {
    val it = iterator()

    fun tailFold(): A = if (!it.hasNext())
        initial
    else
        f(it.next(), { tailFold() })

    return tailFold()
}

Notice that it captures the mutable state of iterator in its closure, which can lead to some weird bugs if those lambdas are executed out of order.

Also its naive usages tend to produce quite ineffective code given the lack of specialized data structures such as Scala’s streams. For example this straightforward way to copy sequence will result in O(n^2/2) complexity and O(n) stack size.

val seqCopy = seq.foldRight(emptySequence<Int>()) {
    e, tail -> sequenceOf(e) + Sequence { tail().iterator() }
}