Понимание рекурсивно определенного списка (fibs с точки зрения zipWith)

Question

Я изучаю Haskell и наткнулся на следующий код:

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

что у меня немного проблем с разбором, с точки зрения того, как это работает. Это очень аккуратно, я понимаю, что больше ничего не нужно, но я хотел бы понять, как Хаскеллу удается "заполнять" выдумки, когда я пишу:

take 50 fibs

Любая помощь?

Спасибо!

Answer 1

Я дам немного объяснения того, как это работает внутри. Во-первых, вы должны понимать, что Haskell использует для своих значений то, что называется thunk. Thunk - это, по сути, значение, которое еще не было вычислено - его следует рассматривать как функцию от 0 аргументов. Всякий раз, когда Хаскелл хочет, он может оценить (или частично оценить) блок, превратив его в реальную ценность. Если это только частично оценивает thunk, тогда получающееся значение будет иметь больше thunk.

Например, рассмотрим выражение:

(2 + 3, 4)

На обычном языке это значение будет храниться в памяти как (5, 4), но в Haskell он хранится как (<thunk 2 + 3>, 4), Если вы спросите о втором элементе этого кортежа, он скажет вам "4", не добавляя 2 и 3 вместе. Только если вы попросите первый элемент этого кортежа, он оценит thunk и поймет, что это 5.

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

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

Это помогает визуализировать текущие знания Хаскелла о трех выражениях: fibs, tail fibs а также zipWith (+) fibs (tail fibs), Предположим, что Haskell начинает, зная следующее:

fibs                         = 0 : 1 : <thunk1>
tail fibs                    = 1 : <thunk1>
zipWith (+) fibs (tail fibs) = <thunk1>

Обратите внимание, что 2-й ряд - это только первый, сдвинутый влево, а 3-й ряд - первые два ряда, которые суммируются.

Спросить take 2 fibs и вы получите [0, 1], Haskell не нужно дополнительно оценивать вышеупомянутое, чтобы выяснить это.

Спросить take 3 fibs и Haskell получит 0 и 1, а затем поймет, что ему нужно частично оценить thunk. Для того, чтобы полностью оценить zipWith (+) fibs (tail fibs), он должен суммировать первые две строки - он не может сделать это полностью, но он может начать суммировать первые две строки:

fibs                         = 0 : 1 : 1: <thunk2>
tail fibs                    = 1 : 1 : <thunk2>
zipWith (+) fibs (tail fibs) = 1 : <thunk2>

Обратите внимание, что я заполнил "1" в 3-й строке, и он автоматически появился и в первой, и во второй строке, поскольку все три строки совместно используют один и тот же блок (воспринимайте его как указатель, который был записан). И поскольку он не закончил оценку, он создал новый thunk, содержащий остальную часть списка, если это когда-либо понадобится.

Это не нужно, потому что take 3 fibs готово: [0, 1, 1], Но теперь, скажем, вы просите take 50 fibs; Haskell уже помнит 0, 1 и 1. Но он должен продолжать идти. Итак, продолжается суммирование первых двух строк:

fibs                         = 0 : 1 : 1 : 2 : <thunk3>
tail fibs                    = 1 : 1 : 2 : <thunk3>
zipWith (+) fibs (tail fibs) = 1 : 2 : <thunk3>

...

fibs                         = 0 : 1 : 1 : 2 : 3 : <thunk4>
tail fibs                    = 1 : 1 : 2 : 3 : <thunk4>
zipWith (+) fibs (tail fibs) = 1 : 2 : 3 : <thunk4>

И так до тех пор, пока он не заполнит 48 столбцов 3-го ряда и, таким образом, не сработает первые 50 чисел. Haskell оценивает столько, сколько ему нужно, и оставляет бесконечный "остаток" последовательности в виде объекта thunk на тот случай, если он когда-либо понадобится.

Обратите внимание, что если вы впоследствии попросите take 25 fibsHaskell не оценит его снова - он просто возьмет первые 25 чисел из списка, который он уже рассчитал.

Изменить: Добавлен уникальный номер для каждого thunk, чтобы избежать путаницы.

Answer 2

Я написал статью об этом некоторое время назад. Вы можете найти это здесь.

Как я уже упоминал, прочитайте главу 14.2 в книге Пола Худака "Школа выражений Хаскеля", где он говорит о рекурсивных потоках на примере Фибоначчи.

Примечание: хвост последовательности - это последовательность без первого элемента.

| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | Последовательность Фибоначчи (Фибс)          |
|---+---+---+---+----+----+----+----+------------------------------------|
| 1 | 2 | 3 | 5 |  8 | 13 | 21 | 34 | хвост последовательности Fib (tail fibs)   |
|---+---+---+---+----+----+----+----+------------------------------------|

Добавьте два столбца: добавьте fib (tail fibs), чтобы получить хвост хвоста последовательности fib

|---+---+---+---+----+----+----+----+------------------------------------|
| 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | хвост хвоста последовательности Фибоначчи |
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |

добавить Fibs (хвостовые Fibs) можно записать как ZipWith (+) FIBS (хвостовые FIBS)

Теперь все, что нам нужно, это простое поколение, начиная с первых 2 чисел Фибоначчи, чтобы получить полную последовательность Фибоначчи.

1: 1: zipWith (+) выдумки (задние выдумки)

Примечание. Это рекурсивное определение не будет работать на типичном языке, который требует оценки. Это работает в haskell, поскольку это делает ленивую оценку. Таким образом, если вы запрашиваете первые 4 числа Фибоначчи, возьмите 4 фибра, haskell только вычисляет достаточно последовательности, как требуется.

Answer 3

Здесь можно найти очень похожий пример, хотя я не полностью его рассмотрел, возможно, он мне поможет.

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

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

Haskell не будет ничего оценивать, пока его не заставят, что называется Lazy Evaluation, что само по себе является прекрасной концепцией.

Итак, давайте предположим, что нас попросили только сделать take 3 fibs Haskell хранит fibs перечислить как 0:1:another_list, так как нас попросили take 3 мы можем также предположить, что он хранится как fibs = 0:1:x:another_list а также (tail fibs) = 1:x:another_list а также 0 : 1 : zipWith (+) fibs (tail fibs) будет тогда 0 : 1 : (0+1) : (1+x) : (x+head another_list) ...

При сопоставлении с образцом Хаскель знает, что x = 0 + 1 Так что ведет нас к 0:1:1,

Мне будет действительно интересно, если кто-то знает некоторые правильные детали реализации. Я могу понять, что методы Lazy Evaluation могут быть довольно сложными, хотя.

Надеюсь, что это помогает в понимании.

Обязательный отказ от ответственности: пожалуйста, примите это с щепоткой соли, это может быть неточно с точки зрения практической реализации, но только в качестве помощи для понимания.

Answer 4

Давайте посмотрим на определение zipWith zipWith f (x:xs) (y:ys) = f x y : zipWith xs ys

Наши выдумки это: fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

За take 3 fibs заменяя определение zipWith а также xs = tail (x:xs) мы получаем 0 : 1 : (0+1) : zipWith (+) (tail fibs) (tail (tail fibs))

За take 4 fibs подставив еще раз, мы получаем 0 : 1 : 1 : (1+1) : zipWith (+) (tail (tail fibs)) (tail (tail (tail fibs)))

и так далее.