Fs2: Add `Stream. foldLazy`

[diesalbla]

The fold method in the Stream class has an inconvenient: it is a strict operation, that needs to pull the whole of the stream to give a result. This is inconvenient when working with unbounded or too-far-bounded streams, which is a more intended use case for fs2.

However, many _reduce_-like operations do not need to evaluate a whole stream, and can instead produce some output after a finite prefix of the input. For such operations, we would need a reduce-like operation that could end as soon as a result is known to be good enough. We may call this foldLazy, or nonStrictFold, in the sense of non-strict evaluation. Such a function would have a Haskell-like signature like the following one:

Stream[F, A] => (B, Boolean) => ( (B, A) => (B, Boolean) ) => Stream[F, B]  

Such that, if the result after some step has on the right-side of the tuple the true value, then the fold would cut out at that point.

This can be implemented in terms of other operations. For instance, a combination of scan and takeWhile and last.

[diesalbla]

Also, other operations could be written in terms of foldLazy, such as find, exists, forall, or fold.

[mpilquist]

Here's a quick implementation of a similar combinator:

def foldLazy[F[_], A, B](s: Stream[F, A])(init: B)(f: (B, A) => Option[B]): Stream[F, B] = {
    def loop(s: Stream[F, A])(acc: B): Pull[F, B, Unit] =
      s.pull.uncons1.flatMap {
        case Some((h, t)) =>
          f(acc, h) match {
            case Some(newAcc) => loop(t)(newAcc)
            case None => Pull.output1(acc)
          }
        case None => Pull.output1(acc)
      }
    loop(s)(init).stream
  }

To make this widely applicable, you'd want to use uncons instead of uncons1 for better performance (tradeoff is more code).

In Gitter, @diesalbla pointed out this implementation used Option[B] instead of (B, Boolean) which results in slightly different semantics (similar to while/through semantic differences). Adjusting the above signature is left as an exercise. ;)

We have a similar combinator in scanChunksOpt -- IIRC, we used to use it for implementing a lot of the other primitives but writing custom recursive pulls for each operation tends to be easier to read & write.

Overall, I think an operation like this is better in user code than in the library. Happy to discuss though.

[Daenyth]

Overall, I think an operation like this is better in user code than in the library.

Can you elaborate on the reasoning? I feel like having the guideline posted would be helpful for the project.

Aside, has anyone started an "fs2-utils"-like library for this sort of thing? It's the kind of code that many projects could need to write, and having it as more of a collective commons would be higher quality than what any individual codebase might produce

[mpilquist]

@Daenyth Being a combinator library, there's a huge number of combinators that could be written and if we added every combinator folks found a use for, we'd have a huge API that's impossible to fully understand. Instead, we have to strike a balance between useful combinators and API size. So there's a subjective evaluation / gut-feel involved in trying to predict which combinators should exist in the library and which should be written in user code. Because of the subjective nature, we'll often get this wrong, and hence, feedback from users on desired combinators is important. If lots of independent users all find a need for a particular combinator, then perhaps it merits inclusion.

Also, one of FS2's main strengths is the Pull API, which lets folks write recursive stream algorithms in a declarative, expressive, and elegant way. This is really important in context of deciding when to add new combinators, as it is significantly easier to write combinators for FS2 than other libraries.

While this isn't a particularly satisfying answer, folks can always ask in a GitHub issue before PR-ing something -- that will at least jump start the discussion.

As for this particular combinator, I haven't heard folks ask about such functionality very often -- the need to do a finite fold and then discard remainder of the stream. Maybe I could see writing this as a pull instead, that returned a Pull[F, Nothing, (B, Stream[F, A])]. Still, I'd want to hear from more folks before adding what seems like a very specialized combinator.

[mpilquist]

Closing this one due to inactivity.