gpt4 book ai didi

list - Haskell 无限递归

转载 作者:行者123 更新时间:2023-12-04 22:43:39 25 4
gpt4 key购买 nike

以下函数计算斐波那契数列:

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

如果我们运行它,我们将得到一个无限列表,但是递归是如何工作的呢?如果函数不断调用自己,为什么它会在屏幕上打印数字?如果您能解释编译器如何管理调用,我将不胜感激。

最佳答案

我画了一张图,你可能会觉得有帮助。
请注意 zipWtih op (x:xs) (y:xs) = (op x y):zipWith xs ys ,这就是 zipWtih似乎沿着列表“移动”。它正在读取元素并吐出总和:

pic with coloured pointers

这是更详细的分步评估。 (虽然我会粘贴那里的副本,但内存中只有一个副本。)我将使用 ....对于我懒得写出来的东西。

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

请注意,现在我们知道 zipWith (+) fib (tail fib) = 1:..... .
    = 0:1:1:zipWith (+) (1:1: ....) (1:......)
= 0:1:1:(1+1):zipWith (+) (1:(1+1): .....) ((1+1):....)
= 0:1:1:2:zipWith (+) (1:2: .....) (2:....)

我会快一点:
    = 0:1:1:2:(1+2):zipWith (+) (2: .....) (....)
= 0:1:1:2:3 :zipWith (+) (2:3 .....) (3:....)
= 0:1:1:2:3:(2+3):zipWith (+) (3:(2+3):.....) ((2+3):.....)
= 0:1:1:2:3:5 :zipWith (+) (3:5:.....) (5:.....)
= 0:1:1:2:3:5:8 :zipWith (+) (5:8:....) (8:......)
= 0:1:1:2:3:5:8:13 :zipWith (+) (8:13:....) (13:......)
= 0:1:1:2:3:5:8:13:21:zipWith (+) (13:21....) (21:......)

在每个阶段, zipWith 的最后两个参数函数就像指向 fib 上方(一个和两个位置)的指针。比我们目前的列表。

关于list - Haskell 无限递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37243102/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com