当累加器满足一定条件时，如何从haskell的折叠函数中爆发？

Question

在将someFunction应用于列表的每个元素之后，我正在计算列表的和，如下所示：

sum (map someFunction myList)

someFunction资源非常多，所以为了优化它，我想停止计算超过某个阈值的和。

似乎我需要使用折叠，但如果累加器达到阈值，我不知道如何突破它。我的猜测是以某种方式组成fold和takeWhile，但我不太确定是如何组成的。

Answer 1

其中一个选项是使用扫描函数，它返回foldl的中间计算列表。

因此，scanl1 (+) (map someFunction myList)将返回计算的中间和。而且，由于Haskell是一种懒惰的语言，在需要它之前，它不会计算myList的所有值。例如：

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

将计算someFunction 5次并返回这5项结果的列表。

在此之后，您可以使用takeWhile或dropWhile，并在特定条件为True时停止计算。例如：

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

当数字之和达到1000并返回1035时，将停止计算。

Answer 2

另一种技术是使用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)

若要忽略退出状态，只需使用either id id编写。

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

Answer 3

使用有界加法运算符代替(+)和foldl。

foldl (\b a -> b + if b > someThreshold then 0 else a) 0 (map someFunction myList)

因为Haskell不是严格的，所以只有对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，您可以看到trace "foo"只执行5次，而不是20次。

但是，您应该使用来自foldl的严格版本foldl'，而不是Data.Foldable.