你将如何在 Haskell 中（重新）实现迭代？

Question

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

（您可能知道）iterate 是一个接受函数和起始值的函数。然后它将函数应用于起始值，然后将相同的函数应用于最后的结果，依此类推。

Prelude> take 5 $ iterate (^2) 2
[2,4,16,256,65536]
Prelude> 

结果是一个无限列表。 （这就是我使用 take 的原因）。 我的问题是，您如何在 Haskell 中实现自己的 iterate' 函数，仅使用基础知识 ((:) (++) lambdas、pattern匹配、守卫等）？

（哈斯克尔初学者在这里）

Answer 1

嗯，iterate 构造了一个由 a 递增的无限值列表 f。因此，我首先编写一个函数，将一些值 a 添加到通过使用 f a 递归调用 iterate 构建的列表中：

iterate :: (a -> a) -> a -> [a]
iterate f a = a : iterate f (f a)

由于惰性求值，仅构建列表的该部分将评估计算我的函数值所必需的。

Answer 2

另请注意，您可以在报告的 Standard Prelude< 中找到基本 Haskell 函数范围的简明定义/a>.

阅读这个简单的定义列表，这些定义本质上是从原始基元中引导出一个丰富的库，在提供“haskell 方式”的窗口方面非常有教育意义，并且令人大开眼界。

我记得很早的时候读到的一个顿悟时刻：data Bool = False |确实如此。

Answer 3

您已经获得了它的最简单的实现；然而，还有其他方法。

一种方法是使用高阶函数，如下所示：

import Data.List (unfoldr)

iterate f x = unfoldr (\x -> Just (x, f x)) x

函数 unfoldr 是一个用于创建列表的高阶函数。这是它最直接的实现：

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr step b = case step b of 
  Nothing -> []
  Just (a, b') -> a : unfoldr step b'

与 foldr 抽象减少列表的直接递归的方式相同，unfoldr 抽象创建它们的直接递归。