Haskell中有任何终止折叠吗？

Question

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

例如，我需要找到前5个大于5的数字。我决定使用Either进行终止，并且我的代码如下所示：

    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 > 3 then (x : acc) else acc)

还有其他更聪明/通用的方法吗？

Answer 1

具有合并功能的

通常具有提前终止的倍数为foldr，在第二个参数中该合并函数不受限制。但是，它的信息流是从右到左（如果有），而您希望它是从左到右。

一种可能的解决方案是使foldr作为left折叠起作用，然后可以使其尽早停止：

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