list - 如何在 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直接到一个列表，但它应该对列表元素进行操作。 (这就是您的错误消息的原因。)

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