haskell - 如果 "output"值与被迭代的值不同，那么前奏迭代的替代方案是什么？

Question

我遇到了一种模式，我从种子值 x 开始。并在每一步生成一个新的种子值和一个要输出的值。我想要的最终结果是输出值列表。这可以用以下函数表示:

my_iter :: (a -> (a, b)) -> a -> [b]
my_iter f x = y : my_iter f x'
   where (x',y) = f x

使用它的一个人为的例子是生成斐波那契数:

fibs:: [Integer]
fibs = my_iter (\(a,b) -> let c = a+b in ((b, c), c)) (0,1)
-- [1, 2, 3, 5, 8...

我的问题是我有一种感觉，很可能有一种更惯用的方式来做这种事情。我的功能有哪些惯用的替代方法？

我现在能想到的只有 iterate来自Prelude，但它们也有一些不足之处。

一种方法是先迭代，然后再映射

my_iter f x = map f2 $ iterate f1 x
    where f1 = fst . f
          f2 = snd . f

但是，如果没有自然的方法将 f 拆分为单独的 f1 和 f2 函数，这可能看起来很难看。 (在人为的斐波那契案例中，这很容易做到，但在某些情况下，生成的值不是种子的“独立”函数，因此拆分事物并不那么简单)

另一种方法是将“输出”值与种子一起元组，并使用单独的步骤将它们分开(有点像排序事物的“施瓦茨变换”):

my_iter f x = map snd . tail $ iterate (f.fst) (x, undefined)

但这似乎很奇怪，因为我们必须记住忽略生成的值以获取种子((f.fst)位)并添加我们需要一个“未定义”值作为第一个虚拟生成值。

Answer 1

如前所述，您想要的功能是 unfoldr .顾名思义，它与foldr相反。 ，但确切地了解为什么这是真的可能会很有启发性。这是 foldr 的类型:

(a -> b -> b) -> b -> [a] -> b

前两个参数是获取 b 类型的方法。 ，并对应于列表的两个数据构造函数:

[]  :: [a]
(:) :: a -> [a] -> [a]

...其中每次出现 [a]替换为 b .注意 []案例产生 b在没有输入的情况下，我们可以将两者合并为一个函数，取 Maybe (a, b)作为输入。

(Maybe (a, b) -> b) -> ([a] -> b)

额外的括号表明这本质上是一个将一种转换转换为另一种转换的函数。

现在，只需反转两个转换的方向:

(b -> Maybe (a, b)) -> (b -> [a])

结果正是 unfoldr 的类型.

这展示的基本思想也可以类似地应用于其他递归数据类型。