Haskell 无限递归 [英] Haskell infinite recursion

问题描述

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

The following function computes the Fibonacci sequence:

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

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

If we run it, we will get an infinite list, but how does the recursion work? Why does it get to print numbers on the screen if it the function keeps calling itself? I would appreciate if you could explain how the compiler manages the calls.

推荐答案

我画了一张图，你可能会觉得有用.
请注意 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.

这篇关于Haskell 无限递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！