当累加器满足一定条件时,如何从haskell的折叠函数中突破？

Question

我在应用someFunction它的每个元素之后计算列表的总和,如下所示:

sum (map someFunction myList)

someFunction 是非常重的资源,所以要优化它我想停止计算总和,如果它超过一定的阈值.

看起来我需要使用折叠,但如果累加器达到阈值,我不知道如何突破.我的猜测是以某种方式组成fold,takeWhile但我不确定如何.

Answer 1

其中一个选项是使用scanl函数,它返回一个中间计算列表foldl.

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

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

将计算someFunction5次并返回这5个结果的列表.

之后,您可以使用takeWhile或dropWhile并在某个条件时停止计算True.例如:

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

当数字总和达到1000并返回时,将停止计算1035.

Answer 2

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