当累加器满足特定条件时，如何从 haskell 中的折叠函数中跳出？

Question

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

sum (map someFunction myList)

someFunction 占用大量资源，因此为了优化它，如果总和超过某个阈值，我想停止计算总和。

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

Answer 1

你可以尝试制作你自己的sum函数，也许称它为boundedSum需要

一个Integer上限
一个[Integer]求和
一个"sum up until this point"值要与上限进行比较

和returns列表的总和。

    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

我认为如果在当前元素超过 upperBound 之前的总和，您将不会 "eat up" 更多列表。

编辑：this question 的答案提出了比我更好的技术，而且问题本身看起来与你的非常相似。

Answer 2

其中一个选项是使用 scanl 函数，其中 return 是 foldl 的中间计算列表。

因此，scanl1 (+) (map someFunction myList) 将 return 您计算的中间总和。由于 Haskell 是一种惰性语言，它不会计算 myList 的所有值，直到您需要它为止。例如：

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

将计算someFunction 5次，return这5次结果的列表。

之后，您可以使用 takeWhile or dropWhile 并在某个条件为 True 时停止计算。例如：

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

将停止计算，当数字总和达到1000且returns 1035.

Answer 3

这是一个可能的解决方案：

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

剖析：

列出您的起始列表（示例中为 [1..]）
映射您的昂贵函数 ((^2))
计算部分和scanl (+) 0
在部分和变得太大后停止（保留那些(<=100)）
取最后一个

如果性能很重要，也可以尝试 scanl'，这可能会有所改善。

Answer 4

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

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

因为 Haskell 是非严格的，所以只对评估 if-then-else 所必需的 someFunction 调用本身进行评估。 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，您应该使用 Data.Foldable.

中的严格版本 foldl'

Answer 5

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

这将按照您的要求进行操作，而无需像 scanl' 那样构建中间列表（并且 scanl 甚至会导致在此之上建立 thunks）：

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

比照。相关 wiki page.

Answer 7

使用 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

然后申请

sumUntil 10 (map someFunction myList)

Answer 8

这个 post 已经有点老了，但我想提一种方法来概括上面 @trevor-cook 的好代码，以打破折叠，并有额外的可能性 return 不是只有默认值或累加器，还有满足中断条件的列表的索引和元素：

import Control.Monad (foldM)

breakFold step initialValue list exitCondition exitFunction = 
  either id (exitFunction (length  list) (last list)) 
      (foldM f initialValue (zip [0..] list))
    where f acc (index,x)
            | exitCondition index x acc 
                        = Left (exitFunction index x acc)
            | otherwise = Right (step index x acc)

同样只需要导入foldM。用法示例如下：

mysum thresh list = breakFold (\i x acc -> x + acc) 0 list 
                         (\i x acc -> x + acc > thresh) 
                         (\i x acc -> acc)
myprod thresh list = breakFold (\i x acc -> x * acc) 1 list 
                          (\i x acc -> acc == thresh) 
                          (\i x acc -> (i,x,acc))

returning

*myFile> mysum 42 [1,1..]
42
*myFile> myprod 0 ([1..5]++[0,0..])
(6,0,0)
*myFile> myprod 0 (map (\n->1/n) [1..])
(178,5.58659217877095e-3,0.0)

通过这种方式，可以使用索引和最后计算的列表值作为进一步功能的输入。

Answer 9

尽管这个 post 年代久远，但我会添加一个可能的解决方案。我喜欢延续，因为我发现它们在流程控制方面非常有用。

breakableFoldl
  :: (b -> a -> (b -> r) -> (b -> r) -> r)
  -> b
  -> [a]
  -> (b -> r)
  -> r
breakableFoldl f b (x : xs) = \ exit ->
    f b x exit $ \ acc ->
        breakableFoldl f acc xs exit
breakableFoldl _ b _ = ($ b)

breakableFoldr
  :: (a -> b -> (b -> r) -> (b -> r) -> r)
  -> b
  -> [a]
  -> (b -> r)
  -> r
breakableFoldr f b l = \ exit ->
  fix (\ fold acc xs next ->
    case xs of
      x : xs' -> fold acc xs' (\ acc' -> f x acc' exit next)
      _ -> next acc) b l exit

exampleL = breakableFoldl (\ acc x exit next ->
    ( if acc > 15
      then exit
      else next . (x +)
    ) acc
  ) 0 [1..9] print

exampleR = breakableFoldr (\ x acc exit next ->
    ( if acc > 15
      then exit
      else next . (x +)
    ) acc
  ) 0 [1..9] print

当累加器满足特定条件时，如何从 haskell 中的折叠函数中跳出？

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

haskell

functional-programming

fold