时间戳

首页 > 解决方案 > Haskell 中是否有任何终止折叠？

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

问题描述

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

例如，我需要找到大于 5 的前 3 个数字。我决定使用 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 > 5 then (x : acc) else acc)

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

标签： haskellfunctional-programmingexitfold

解决方案

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

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

让我们定义一个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]

推荐阅读