Генерация последовательности Фибоначчи

Question

Я писал генератор последовательности Фибоначчи, и я пытался понять следующий код на Хаскеле

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Я понимаю что zipWith есть, но я точно не знаю, как выполняется программа и почему она генерирует все числа Фибоначчи. Я пытался понять, почему он не прекращает использовать концепцию среды в функциональных языках следующим образом:

Первоначально, потому что ленивая оценка Haskell, связывание в env должно быть fibs : [1,1,x]затем оценить fibsпереводчик оценивает x который zipWith (+) fibs (tail fibs) в этом случае. При оценке zipWith, это становится fibs : [1,1,2,x]опять же из-за ленивой оценки Haskell. А также fibs в env связан с [1,1,2,x] в это время. Тем не менее, чтобы полностью оценить fibsпродолжает оценивать x и мы вернемся к предыдущим шагам.

Это правильно?

Кроме того, я заметил, что когда я запустил программу выше в ghci, он мгновенно запрашивает последовательность Фибоначчи, которую он в настоящее время вычислил, почему? Разве он не должен печатать результат после завершения всех вычислений?

Answer 1

Итак, большая часть ваших рассуждений верна. В частности, вы правильно описали, как каждый новый элемент списка оценивается с точки зрения более старых. Вы также правы, чтобы полностью оценить fibs потребовалось бы повторить шаги, которые вы обрисовали в общих чертах, и, фактически, зациклился бы навсегда.

Ключевой компонент, который вам не хватает, заключается в том, что нам не нужно полностью оценивать список. Привязка как fibs = ... просто присваивает имя выражению; это не требует оценки всего списка. Haskell будет оценивать только столько списка, сколько ему нужно для запуска main, Так, например, если наш main является

main = print $ fibs !! 100

Haskell рассчитает только первые 100 элементов fibs (следуя шагам, которые вы обрисовали в общих чертах), но вам больше не понадобится, и цикл не будет длиться вечно.

Более того, даже если мы оцениваем всю вещь (которая будет работать вечно), мы можем использовать части, которые мы рассчитали, по мере продвижения вперед. Это именно то, что происходит, когда вы видите значение fibs в ghci: он печатает столько, сколько может, сколько вычисляется для каждого элемента, и ему не нужно ждать, пока весь список не будет готов.

Видеть Строгость в GHCi

Вы можете увидеть, сколько из списка оценивается в ghci с использованием :sprint команда, которая будет печатать структуру данных Haskell с _ для частей, которые еще не были оценены (так называемые "громоотводы"). Вы можете использовать это, чтобы увидеть, как fibs оценивается в действии:

Prelude> let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = _

К сожалению, это не то, что мы ожидали! Фактически, это тот случай, когда отсутствие ограничения мономорфизма является проблемой! fibs приобретает полиморфный тип

Prelude> :t fibs
fibs :: Num a => [a]

это означает, что он ведет себя как вызов функции каждый раз, когда вы его используете, а не как нормальное значение. (В фоновом режиме GHC реализует создание Num Тип класса, как передача в словаре fibs; это реализовано как NumDictionary a -> [a] функция).

Чтобы действительно понять, что происходит, нам нужно сделать fibs мономорфно явно. Мы можем сделать это, загрузив его из модуля, где ограничение активно, или предоставив ему явную сигнатуру типа. Давайте сделаем последнее:

Prelude> let fibs :: [Integer]; fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Prelude> :sprint fibs
fibs = _
Prelude> print $ fibs !! 10
89
Prelude> :sprint fibs
fibs = 1 : 1 : 2 : 3 : 5 : 8 : 13 : 21 : 34 : 55 : 89 : _

И вот вы здесь: вы можете видеть, какие части списка нужно было оценить, а какие нет, чтобы получить 10-й элемент. Вы можете поиграть с другими списками или другими ленивыми структурами данных, чтобы лучше понять, что происходит в фоновом режиме.

Кроме того, вы можете взглянуть на мой пост в блоге об этой лени. Более подробно о fibs пример (с диаграммами!) и рассказывает о том, как использовать этот подход для общего запоминания и динамического программирования.