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.
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
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.
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.
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() }
}