How to break out from a fold function in haskell when the accumulator met a certain condition?
One of the options would be using scanl function, which returns a list of intermediate calculations of foldl
.
Thus, scanl1 (+) (map someFunction myList)
will return the intermediate sums of your calculations. And since Haskell
is a lazy language it won't calculate all the values of myList
until you need it. For example:
take 5 $ scanl1 (+) (map someFunction myList)
will calculate someFunction
5 times and return the list of these 5 results.
After that you can use either takeWhile or dropWhile and stop the calculation, when a certain condition is True
. For example:
head $ dropWhile (< 1000) $ scanl1 (+) [1..1000000000]
will stop the calculation, when sum of the numbers reaches 1000 and returns 1035
.
Another technique is to use a foldM
with Either
to capture the early termination effect. Left
signals early termination.
import Control.Monad(foldM)
sumSome :: (Num n,Ord n) => n -> [n] -> Either n n
sumSome thresh = foldM f 0
where
f a n
| a >= thresh = Left a
| otherwise = Right (a+n)
To ignore the exit condition, just compose with either id id
.
sumSome' :: (Num n,Ord n) => n -> [n] -> n
sumSome' n = either id id . sumSome n
Use a bounded addition operator instead of (+)
with foldl
.
foldl (\b a -> b + if b > someThreshold then 0 else a) 0 (map someFunction myList)
Because Haskell is non-strict, only calls to someFunction
that are necessary to evaluate the if-then-else
are themselves evaluated. fold
still traverses the entire list.
> foldl (\b a -> b + if b > 10 then 0 else a) 0 (map (trace "foo") [1..20])
foo
foo
foo
foo
foo
15
sum [1..5] > 10
, and you can see that trace "foo"
only executes 5 times, not 20.
Instead of foldl
, though, you should use the strict version foldl'
from Data.Foldable.