Как выйти из функции fold в haskell, когда аккумулятор выполнил определенное условие?

Одним из вариантов может быть использование scanl функция, которая возвращает список промежуточных вычислений 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.

Другой метод заключается в использовании 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

Используйте ограниченный оператор сложения вместо (+) с 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..

Вы можете попробовать создать свою собственную функцию sum, возможно, назовите ее boundedSum, которая принимает

1. Integer верхняя граница

2. [Integer] для суммирования

3. значение "суммировать до этой точки" для сравнения с верхней границей

и возвращает сумму списка.

    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

Я думаю, что таким образом вы не будете «съедать» больше списка, если сумма будет до тех пор, пока текущий элемент не превысит верхнюю границу.

EDIT: ответы на этот вопрос предлагает лучшие методы, чем мой, и сам вопрос очень похож на ваш.

Это сделает то, о чем вы спрашиваете, без создания промежуточного списка, как 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

ср. связанная вики-страница.

Это возможное решение:

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

Рассеченный:

• возьмите свой стартовый список ([1..] в примере)
• сопоставьте свою дорогую функцию ((^2))
• вычислять частичные суммы scanl (+) 0
• остановитесь после того, как частичные суммы станут слишком большими (сохраните эти (<=100))
• взять последний

Если производительность имеет значение, также попробуйте scanl', которая может ее улучшить.

Что-то вроде этого с использованием until :: (a -> Bool) -> (a -> a) -> a -> a из Prelude

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)