How to break out from a fold function in haskell when the accumulator met a certain condition?

Question

I'm calculating the sum of a list after applying someFunction to every element of it like so:

sum (map someFunction myList)

someFunction is very resource heavy so to optimise it I want to stop calculating the sum if it goes above a certain threshold.

It seems like I need to use fold but I don't know how to break out if it if the accumulator reaches the threshold. My guess is to somehow compose fold and takeWhile but I'm not exactly sure how.

Answer 1

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 status, just compose with either id id.

sumSome' :: (Num n,Ord n) => n -> [n] -> n
sumSome' n = either id id . sumSome n

Answer 2

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.

Answer 3

This will do what you ask about without building the intermediate list as scanl' would (and scanl would even cause a thunks build-up on top of that):

foldl'Breaking break reduced reducer acc list = 
    foldr cons (\acc -> acc) list acc 
          where 
          cons x r acc | break acc x = reduced acc x 
                       | otherwise   = r $! reducer acc x

cf. related wiki page.