Support for early termination

[maoe]

Is there a good way to support early termination in the foldl library? Currently fold has to go though the list until the end even if head is passed.

[Gabriella439]

No, this library does not support any way for the Fold to indicate that no further input is necessary

[michaelt]

There is an interesting systematic attempt at this in https:/effectfully/prefolds One simple-minded point in defense of the foldl approach is that the emphasis of the library is on combining simultaneous folds e.g. liftA3 (,,) L.head (L.index 17) L.sum so though individual stock folds could exit early, their combinations tend to consume all of the input.

[maoe]

@michaelt Thanks for the info. That's interesting. I was thinking of something simpler like x -> a -> Maybe x or x -> a -> (Bool, x) for the step function in Fold. The argument about early termination with composition is a good point but I think it's still useful to support it.

I guess I'll see if I can support it without sacrificing the simple API and good performance.

[rizo]

@Gabriel439 could you please elaborate on the decision of not including early termination in Foldl? Are you aware of any structures similar to Foldable that support termination in reducing functions?

[Gabriella439]

@rizo: I'm not aware of a similar structure that supports (A) early termination and (B) Applicative composition of Folds

The main reason why foldl does not do so is because the scope of the library is to be a replacement in spirit for Data.List.foldl. That's why the signature of the Fold type exactly matches the arguments you pass to foldl (which also does not have a termination check). There is a similar library named folds with a broader scope where this might be a better fit:

http://hackage.haskell.org/package/folds