且构网

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

Haskell无限递归

更新时间:2023-02-27 08:57:02

我画了一幅画,可能会对您有所帮助.
请注意zipWtih op (x:xs) (y:xs) = (op x y):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:......

notice that now we know that 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.