Is there any terminating fold in Haskell?

Question

I need some kind of fold which can terminate if I already have the data I want.

For example I need to find first 3 numbers which are greater than 5. I decided to use Either for termination and my code looks like this:

    terminatingFold :: ([b] -> a -> Either [b] [b]) -> [a] -> [b]
    terminatingFold f l = reverse $ either id id $ fold [] l
      where fold acc [] = Right acc
            fold acc (x:xs) = f acc x >>= flip fold xs

    first3NumsGreater5 acc x =
      if length acc >= 3
        then Left acc
        else Right (if x > 5 then (x : acc) else acc)

Are there some more clever/generic approaches?

Answer 1

The result of your function is a list, and it would be desirable if it were produced lazily, that is, extracting one item from the result should only require evaluating the input list up until the item is found there.

Unfolds are under-appreciated for these kinds of tasks. Instead of focusing on "consuming" the input list, let's think of it as a seed from which (paired with some internal accumulator) we can produce the result, element by element.

Let's define a Seed type that contains a generic accumulator paired with the as-yet unconsumed parts of the input:

{-# LANGUAGE NamedFieldPuns #-}
import Data.List (unfoldr)

data Seed acc input = Seed {acc :: acc, pending :: [input]}

Now let's reformulate first3NumsGreater5 as a function that either produces the next output element from the Seed, of signals that there aren't any more elements:

type Counter = Int

first3NumsGreater5 :: Seed Counter Int -> Maybe (Int, Seed Counter Int)
first3NumsGreater5 (Seed {acc, pending})
  | acc >= 3 =
    Nothing
  | otherwise =
    case dropWhile (<= 5) pending of
      [] -> Nothing
      x : xs -> Just (x, Seed {acc = succ acc, pending = xs})

Now our main function can be written in terms of unfoldr:

unfoldFromList ::
  (Seed acc input -> Maybe (output, Seed acc input)) ->
  acc ->
  [input] ->
  [output]
unfoldFromList next acc pending = unfoldr next (Seed {acc, pending})

Putting it to work:

main :: IO ()
main = print $ unfoldFromList first3NumsGreater5 0 [0, 6, 2, 7, 9, 10, 11]
-- [6,7,9]