迭代可以用折叠来写吗？

Question

前言

我正在尝试将函数反复应用于f给定参数的想法z，从而获得无限列表。

基本上我想要列表[z, f z, f (f z), f (f (f z)), ...]，我可以将其提供给take n，takeWhile whatever或其他东西。

最初我认为由于我要处理的列表是无限的（我正在考虑repeat f），我应该使用foldr，但实际上这是不可能的，因为当foldring 一个无限列表时，累加器通常设置为undefined因为未使用，所以在像foldr (\f (x:xs) -> f x:x:xs) undefined (repeat f)我不会放的东西z。

问题

所以我开始写这个问题，并且，由于弹出的自动建议，我发现它iterate已经存在，并且它的实现是，

{-# NOINLINE [1] iterate #-}
iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)

所以我的问题改变了：是否可以写成iterate折叠？如果是这样，怎么办？如果没有，为什么？

Answer 1

不，或者至少不是以任何惯用的方式。但那是因为foldr它的工具不适合这项工作。foldr是褶皱，或变质作用。这是一种奇特的数学方式，表示它需要聚合数据（在本例中为列表）并生成单个结果（标量，例如数字）。这就是为什么像 之类的操作sum可以直接用 来编写foldr，因为sum从根本上讲是采用聚合数据并产生单一结果。

您想要的是变形，或者一种获取单点数据（z在您的示例中）并从中生成聚合数据的方法。在 Haskell 中，这被恰当地命名为unfoldr.

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

unfoldr以 ab 初始值开始b并调用给定的函数。每次调用该函数时，如果它生成 a Just (a, b')，则我们将其用作a列表的第一个元素，并继续将其b'用作状态值。如果函数返回Nothing，那么我们就停止迭代。

在您的情况下，您想要生成一个无限列表，因此我们将始终返回一个Just值。您可以iterate按照unfoldr如下方式编写。

import Data.List(unfoldr)

iterate' :: (a -> a) -> a -> [a]
iterate' f = unfoldr (\z -> Just (z, f z))