Может ли кто-нибудь объяснить это ленивое решение Фибоначчи?

Question

Это код:

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs) 

При оценке, fibs бесконечный список чисел Фибоначчи. Что я не понимаю, так это то, как список объединяется.

zipWith возвращает список, так что сжать fibs даст это:

0 : 1 : [1] : [1,2] : [1,2,3] 

, потому что 0 : 1 : zipWith (+) [0,1] [1] выходы [1] и zipWith (+) [0,1,1] [1,1] выходы [1,2] и т.д.).

Однако, когда я запускаю код, я получаю правильный результат.

Что я не понимаю здесь?

Answer 1

Ваш «Потому что» не рассказывает всю историю. Вы усекаете списки в «истории до сих пор» и оцениваете с нетерпением, а затем задаетесь вопросом, откуда приходит это. Это не совсем понять, что происходит, так хороший вопрос.

Что получает вычислен, когда вы делаете определение

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs) 

? Очень мало. Вычисление начинается, как только вы начинаете использовать список. Ленивое вычисление происходит только по требованию.

Какой спрос? Вы можете спросить: «Вы [] или x : xs?» и если это последний, вы получаете ручку на куски.

Когда мы спрашиваем, что вопрос о fibs, мы получаем, что

fibs = x0 : xs0 
x0 = 0 
xs0 = 1 : zipWith (+) fibs (drop 1 fibs) 

, но это означает (заменяющие fibs и затем x0)

xs0 = 1 : zipWith (+) (0 : xs0) (drop 1 (0 : xs0)) 

и когда мы спрашиваем снова, мы получаем, что

xs0 = x1 : xs1 
x1 = 1 
xs1 = zipWith (+) (0 : xs0) (drop 1 (0 : xs0)) 

так

xs1 = zipWith (+) (0 : 1 : xs1) (drop 1 (0 : 1 : xs1)) 

, но теперь это становится интересным, потому что мы должны сделать некоторую работу. Просто достаточно работы, чтобы ответить на вопрос, ум? Когда мы смотрим на xs1, мы вынуждаем zipWith, который заставляет drop.

xs1 = zipWith (+) (0 : 1 : xs1) (drop 1 (0 : 1 : xs1)) 
    = zipWith (+) (0 : 1 : xs1) (1 : xs1) 
    = (0 + 1) : zipWith (+) (1 : xs1) xs1 

так

xs1 = x2 : xs2 
x2 = 0 + 1 = 1 
xs2 = zipWith (+) (1 : xs1) xs1 
    = zipWith (+) (1 : 1 : xs2) (1 : xs2) 

См? Мы утверждали, что мы все еще знаем первые два элемента одного zip-списка и первый элемент другого. Это означает, что мы сможем доставить следующий вывод и обновить наш «буфер». Когда мы смотрим на xs2, мы получаем

xs2 = zipWith (+) (1 : 1 : xs2) (1 : xs2) 
    = (1 + 1) : zipWith (1 : xs2) xs2 
xs2 = x3 : xs3 
x3 = 1 + 1 = 2 
xs3 = zipWith (1 : xs2) xs2 
    = zipWith (1 : 2 : xs3) (2 : xs3) 

и мы хорошо идти снова!

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

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

Ключ в том, что ленивы, «по требованию» вычисление означает, что мы не должны усечь перечни просто элементы, которые мы можем видеть при запуске процесса. Нам просто нужно знать, что мы всегда можем сделать следующий шаг.