list - 如何在 Haskell 中定义对函数的递归调用列表
问题描述
我想做的是定义一个这样的函数:
[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)
如何创建一个像这样起作用的列表?
解决方案
我喜欢你的尝试
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
推荐阅读
- android - 滑动刷新recyclerview重复项json
- python - 如何对字典进行排序并按字母顺序设置?
- java - 如何使用 Postman 发布到 Java 中的 API?
- javascript - 如何在循环中替换图像
- android - 单击浮动操作栏时未加载新活动
- python - 如何在底部获取总计列
- javascript - JavaScript 对象索引 - 一个键的多个值
- git - 为什么 Gitlab CI 无法获取 git 子模块但在随后的推送中检查出子模块?
- sql - 根据 max(cases) 和 min(date) 选择所有行
- python - 无法在 conda 中导入 pcl