如何在Haskell中定义对函数的递归调用列表

Question

我想做的是定义一个这样的函数：

[f 0, f f 0, f f f 0, f f f f 0, f f f f f 0..]

换句话说，每个元素是通过函数运行的最后一个元素。

我已经尝试过几次，以通过调用带有预定义的前几个元素的列表来使它以类似于我在Haskell中看到的斐波那契数列的方式工作：

fib = 0 : 1 : zipWith (+) fib (tail fib)

ls = 0 : f 0 : f (last ls)

如果我将f定义为简单的addOne函数，例如：

f =（+1）

我收到此错误：

<interactive>:124:5: error:
* Occurs check: cannot construct the infinite type: a ~ [a]
  Expected type: [[a]]
    Actual type: [a]
* In the expression: 0 : (f 0) : f (last y)
  In an equation for `y': y = 0 : (f 0) : f (last y)
* Relevant bindings include
    y :: [[a]] (bound at <interactive>:124:1)

如何创建一个具有以下功能的列表？

Answer 1

我喜欢你的尝试

ls = 0 : f 0 : f (last ls)

这些是它的问题：

• 没有类型签名。始终编​​写类型签名。从技术上讲，它们是可选的，但是男孩可以帮助您了解正在发生的事情以及您甚至想要什么。
• 您正在尝试f直接应用于列表，但是应该对list元素进行操作。（这就是您的错误消息的原因。）
• last在无限列表上可能没有好处。无论如何，这不是您想要的：f应该应用于尾巴的所有元素。那就是为什么map。

因此，以下是该尝试的正确而完整的实现：

iterate' :: (a -> a) -> a -> [a]
 -- altn.:  (Int->Int) -> [Int], without x? but always starting from 0
iterate' f x? = ls
 where ls = x? : f x? : map f (tail ls)

注意：这实际上并没有提供，[f 0, f (f 0), f (f (f 0)) ..]但是从开始0。首先f 0，只需删除独立的x?：

iterate' f x? = ls
 where ls = f x? : map f (tail ls)

...但是它不会终止（感谢@WillNess），因为它tail现在将永远递归。但是您实际上并不需要tail！这是正确的定义：

iterate' f x? = ls
 where ls = f x? : map f ls

Answer 2

如果您想自己定义它，而不是使用@WillemVanOnsem指出的迭代，那么简单的原始递归就是您的朋友：

f :: (a -> a) -> a -> [a]
f g x = let new = g x in new `seq` new : f g new

这与iterate相似，除了iterate从您提供的元素（第一个x）而不是函数的第一个应用程序开始：

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

可以通过搜索此类功能并读取在基本包中找到的任何搜索命中的实现来获得自我教育。