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

Question

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

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

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

take 50 fibs

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

Спасибо!

Answer 1

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

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

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

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

Это не нужно, потому что 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 fibs, Haskell больше не будет его оценивать - он просто возьмет первые 25 чисел из списка, который он уже рассчитал.

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

Answer 2

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

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

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

|---+---+---+---+----+----+----+----+------------------------------------|
| 1 | 1 | 2 | 3 |  5 |  8 | 13 | 21 | Fibonacci sequence (fibs)          |
|---+---+---+---+----+----+----+----+------------------------------------|
| 1 | 2 | 3 | 5 |  8 | 13 | 21 | 34 | tail of Fib sequence (tail fibs)   |
|---+---+---+---+----+----+----+----+------------------------------------|

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

|---+---+---+---+----+----+----+----+------------------------------------|
| 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | tail of tail of Fibonacci sequence |
|---+---+---+---+----+----+----+----+------------------------------------|

добавить 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) ...

По шаблонуСоответствующий Haskell знает, что 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)))

и т. Д.