9

我看到了这段代码来生成斐波那契数。

fibs = 1:1:(zipWith (+) fibs (tail fibs))

是否可以编写类似样式的代码来生成无限列表 [1..]？

我在 Haskell 网站上看到了这个关于循环结构的链接。

有一个例子

cyclic = let x = 0 : y
         y = 1 : x
     in  x

我试图以循环方式为我的问题定义一个列表，但未能成功。我想要的是一个根据自身定义的列表，它在 Haskell 中计算为 [1..]。

注意：Haskell[1..]计算结果为[1,2,3,4,5...]而不是[1,1,1...]。

4

3 回答 3

17

以下应该会给你想要的结果：

nats = 1 : map (+1) nats

或者，更惯用地说：

nats = iterate (+1) 1

[1,2,3...]通过使用等式推理，很容易看出为什么第一个片段的计算结果为：

nats = 1 : map (+1) nats 
     = 1 : map (+1) (1 : map (+1) nats) 
     = 1 : map (+1) (1 : map (+1) (1 : map (+1) nats))
     = 1 : 1 + 1 : 1 + 1 + 1 : .... 
     = [1,2,3...]
于 2013-11-03T03:03:52.340 回答
8

是的。

想想如何写出列表中的每个元素：

1
1 + 1
1 + 1 + 1
1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

在每个条目之后，每个后续条目都有一个额外的+ 1. 所以我们要开始，1然后添加1到每个后续元素。然后我们想要获取第二个元素并添加1到之后的所有内容中。

我们可以这样做：

let xs = 1 : map (+ 1) xs

这扩展如下：

1 : map (+ 1) xs
1 : (1 + 1) : map (+ 1) xs
1 : (1 + 1) : ((1 + 1) + 1) : map (+ 1) xs

等等。

于 2013-11-03T03:05:55.807 回答
0

实际上，因为 Haskell 的懒惰是由需要调用的，所以定义了

xs = 1 : map (+1) xs

然后调用 egprint xs继续为

xs
xs  where  xs = 1 : map (+ 1) xs
xs  where  xs = x1 : xs2 ; x1 = 1 ; xs2 = map (+ 1) xs
x1 : xs2  where  xs2 = map (+ 1) (x1 : xs2) ; x1 = 1
x1 : xs2  where  xs2 = (x1+1) : map (+ 1) xs2 ; x1 = 1
x1 : xs2  where  xs2 = x2 : xs3 ; x2 = x1+1 ; xs3 = map (+ 1) xs2 ; x1 = 1
1 : x2 : xs3  where  xs3 = map (+ 1) (x2 : xs3) ; x2 = 2
1 : x2 : xs3  where  xs3 = (x2+1) : map (+ 1) xs3 ; x2 = 2
1 : 2 : x3 : xs4  where  xs4 = map (+ 1) (x3 : xs4) ; x3 = 3
1 : 2 : 3 : x4 : xs5  where  xs5 = map (+ 1) (x4 : xs5) ; x4 = 4
.....

这样就不会n+1通过重复添加1s 来重复计算。n已经计算过了。

我们只是给每个地方一个名字，所以这个名字首先包含一个要执行的计算，然后是它的值。由于名称在其他计算中共享，因此不会重复计算其值。

同样的事情发生在斐波那契数列的计算上。

所以 thenxs确实生成了 list [1,2..]。重复添加的1过程自然表示为iterate (+1) 1，正如在另一个答案中已经指出的那样。

我们也可以将其定义为

nums1 = xs where
        ys = 1 : ys
        xs = zipWith (+) (0 : xs) ys

这也许就是你想要表达的。

通过 zip 定义列表并使其自身移动一步（如在 Fibonacci 列表定义中），映射函数可以在定义当前元素的同时同时访问列表的两个先前元素。

类似地，通过压缩自身移动一步和另一个列表（如nums1上面的定义）来定义列表，使映射函数在定义当前元素的同时访问前一个元素。

我们说“映射函数”是因为zipWith它是二进制的map：

zipWith f xs ys = map (\(x,y) -> f x y) (zip xs ys)
于 2021-09-25T09:00:24.173 回答