Haskell бесконечной рекурсии

Question

Следующая функция вычисляет последовательность чисел Фибоначчи:

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

Если мы запустим его, мы получим бесконечный список, но как рекуррентное работу? Зачем он печатает цифры на экране, если функция продолжает называть себя? Я был бы признателен, если бы вы могли объяснить, как компилятор управляет вызовами.

Answer 1

Я нарисовал изображение, которое может показаться вам полезным.
Обратите внимание, что zipWtih op (x:xs) (y:xs) = (op x y):zipWith xs ys, то есть как zipWtih появляется, чтобы «двигаться» прямо по списку. Он читает элементы и выплевывая суммы:

---

Вот более подробная оценка шаг за шагом. (Хотя я буду вставлять копии того, что там, в памяти есть только одна копия.) Я буду использовать .... для вещей, которые я не могу беспокоить, чтобы их выписать.

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 списка, чем мы в настоящее время.

Answer 2

Одним словом: лень. Список в Haskell больше похож на генератор: он будет вычислять только значения, когда они потребуются чем-то другим.

Например, head [1 , 2+3] не будет выполнять добавление, так как оно не требуется. Аналогично, если мы рекурсивно допустим ones = 1 : ones, то head ones = head (1 : ones) = 1 не нужно оценивать весь хвост.

Вы можете попробовать гадать, что произойдет, если мы выводим пар x, определяются следующим образом:

x = (n, fst x + 1) 

Выше мы используем (отложенную) пару вместо (ленивого) списка, но рассуждения одно и то же , Не оценивайте ничего, если это не нужно чем-то другим.