且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

Haskell 无限递归

更新时间:2023-02-27 08:44:17

我画了一张图,你可能会觉得有用.
请注意 zipWtih op (x:xs) (y:xs) = (op xy):zipWith xs ys,这就是 zipWtih 沿着列表.它正在读取元素并吐出总和:

I've drawn a picture, which you might find helpful.
Note that zipWtih op (x:xs) (y:xs) = (op x y):zipWith xs ys, which is how zipWtih appears to "move" right along the list. It's reading elements and spitting out sums:

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

Here's a more detailed step-by-step evaluation. (Although I'll paste copies of what's there, there's only one copy in memory.) I'll use .... for things I can't be bothered to write out.

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 列表比我们现在更远的指针.

At each stage, the last two arguments to the zipWith function are like pointers to (one and two positions) further up the fib list than we are at present.