Haskell 中是否有任何终止折叠？

Question

如果我已经有了我想要的数据，我需要某种折叠可以终止。

例如，我需要找到前 3 个大于 5 的数字。我决定使用任一终止，我的代码如下所示：

    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)

是否有一些更聪明/通用的方法？

Answer 1

您的函数的结果是一个列表，如果它是惰性生成的，那将是可取的，也就是说，从结果中提取一个项目应该只需要评估输入列表，直到在那里找到该项目。

对于这类任务，展开未被重视。与其专注于“消耗”输入列表，让我们将其视为一个种子，从中（与一些内部累加器配对）我们可以逐个元素地产生结果。

让我们定义一个Seed类型，它包含一个与输入的尚未使用的部分配对的通用累加器：

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

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

现在让我们重新制定first3NumsGreater5一个函数，该函数可以从Seed, 的信号中生成下一个输出元素，即不再有任何元素：

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})

现在我们的主函数可以写成unfoldr：

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

让它工作：

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

Answer 2

通常，能够提前终止的折叠foldr与组合函数一起使用，该函数的第二个参数是非严格的。但是，它的信息流是从右到左（如果有的话），而您希望它是从左到右。

一个可能的解决方案是将foldr函数设为左折叠，然后可以使其提前停止：

foldlWhile :: Foldable t 
           => (a -> Bool) -> (r -> a -> r) -> r 
           -> t a -> r
foldlWhile t f a xs  =  foldr cons (\acc -> acc) xs a
  where
    cons x r acc | t x  =  r (f acc x) 
                 | otherwise  =  acc

您将需要调整它来t测试acc而不是x, 以满足您的目的。

这个函数foldlWhile来自https://wiki.haskell.org/Foldl_as_foldr_alternative，重写了一点。foldl'Breaking从那里开始可能更符合要求。

foldr使用惰性减速器函数可以像unfoldr那样完美地表达核心递归。

而且你的代码已经很懒了：terminatingFold (\acc x -> Left acc) [1..]=> []。这就是为什么我不确定这个答案是否如您所要求的“更聪明”。

编辑：按照@danidiaz的评论，要使其适当懒惰，您必须将其编码为例如

first3above5 :: (Foldable t, Ord a, Num a) 
             => t a -> [a]
first3above5 xs  =  foldr cons (const []) xs 0
   where
   cons x r i | x > 5  =  if i==2 then [x]
                                  else x : r (i+1)
              | otherwise  =  r i

这可以通过抽象测试和计数来进一步概括。

当然，它只是重新实现take 3 . filter (> 5)，但展示了如何使用foldr.