如何在 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

Haskell 已经有一个函数：iterate :: (a -> a) -> a -> [a]。例如：

Prelude> take 10 (iterate (2*) 1)
[1,2,4,8,16,32,64,128,256,512]

您的问题略有不同，因为第一个元素应该是 f 0，而不是 0，但我们可以简单地对其应用 f，或使用 tail :: [a] -> [a]在结果上。例如：

ls :: Num a => (a -> a) -> [a]
ls = tail . flip iterate 0

例如：

Prelude> take 10 (ls (1+))
[1,2,3,4,5,6,7,8,9,10]

Answer 2

或自己滚动：

fn f a = (f a) : (fn f (f a))

main = print $ take 6 $ fn (5+) 1

输出：

[6,11,16,21,26,31]

Answer 3

如果您想自己定义它，而不是使用 @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)

可以通过 hoogling for functions of this type and reading the implementation 在基本包中找到的任何搜索命中获得自我教育。

Answer 4

我喜欢你的尝试

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

这些是它的问题：

没有类型签名。总是写类型签名。从技术上讲，它们是可选的，但天哪，它们有助于了解正在发生的事情以及您甚至想要什么。
您正在尝试将 f 直接应用于列表，但它应该对 列表元素 进行操作。（这就是您的错误消息的原因。）
last 可能不好。无论如何，这不是您想要的：f 应该应用于尾部的 all 元素。这就是 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)

N.B。这实际上并没有给出 [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

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

How to define a list of recursive calls to a function in Haskell

iteration

recursion

haskell

list

higher-order-functions