Clash Royale CLAN TAG#URR8PPP

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

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

someFunction

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.

someFunction

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.

fold

takeWhile

7 Answers
7

One of the options would be using scanl function, which returns a list of intermediate calculations of foldl.

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:

scanl1 (+) (map someFunction myList)

Haskell

myList

take 5 $ scanl1 (+) (map someFunction myList)


will calculate someFunction 5 times and return the list of these 5 results.

someFunction

After that you can use either takeWhile or dropWhile and stop the calculation, when a certain condition is True. For example:

True

head $ dropWhile (< 1000) $ scanl1 (+) [1..1000000000]


will stop the calculation, when sum of the numbers reaches 1000 and returns 1035.

1035

head

Another technique is to use a foldM with Either to capture the early termination effect. Left signals early termination.

foldM

Either

Left

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)


Use a bounded addition operator instead of (+) with foldl.

(+)

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.

someFunction

if-then-else

fold

> 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.

sum [1..5] > 10

trace "foo"

Instead of foldl, though, you should use the strict version foldl' from Data.Foldable.

foldl

foldl'

Data.Foldable.

a

You could try making your own sum function, maybe call it boundedSum that takes

sum

boundedSum

an Integer upper bound

Integer

an [Integer] to sum over

[Integer]

a "sum up until this point" value to be compared with the upper bound

and returns the sum of the list.

boundedSum :: Integer -> [Integer] -> Integer -> Integer
boundedSum upperBound (x : xs) prevSum =
let currentSum = prevSum + x
in
if currentSum > upperBound
then upperBound
else boundedSum upperBound xs currentSum
boundedSum upperBound prevSum =
prevSum


I think this way you won't "eat up" more of the list if the sum up until the current element exceeds upperBound.

EDIT: The answers to this question suggest better techniques than mine and the question itself looks rather similar to yours.

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):

scanl'

scanl

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.

This is a possible solution:

last . takeWhile (<=100) . scanl (+) 0 . map (^2) $ [1..]


Dissected:

[1..]

(^2)

scanl (+) 0

(<=100)

If performance matters, also try scanl', which might improve it.

scanl'

Something like this using until :: (a -> Bool) -> (a -> a) -> a -> a from the Prelude

until :: (a -> Bool) -> (a -> a) -> a -> a

sumUntil :: Real a => a -> [a] -> a
sumUntil threshold u = result

where

(_, result) = until stopCondition next (u, 0)

next :: Real a => ([a], a) -> ([a], a)
next ((x:xs), y) = (xs, x + y)

stopCondition :: Real a => ([a], a) -> Bool
stopCondition (ls, x) = null ls || x > threshold


Then apply

sumUntil 10 (map someFunction myList)


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.