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

Ответ 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]. Haskell не нужно дополнительно оценивать вышесказанное, чтобы это выяснить.

Попросите take 3 fibs, и Хаскелл получит 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-й строке, и она автоматически появилась и в первой, и во второй строке, поскольку все три строки используют один и тот же блок (представьте, что указатель записан в). И поскольку он не завершил оценку, он создал новый раздел, содержащий остальную часть списка, если это когда-либо понадобится.

Это не нужно, потому что 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 чисел из списка, который он уже рассчитал.

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

Ответ 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)   |
|---+---+---+---+----+----+----+----+------------------------------------|

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

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

add fibs (tail fibs) можно записать как zipWith (+) fibs (tail fibs)

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

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

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

Ответ 3

Простой пример, связанный с этим, можно найти здесь, хотя я не полностью его рассмотрел, возможно, из-за некоторой помощи.

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

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

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

Итак, давайте предположим, что нас попросили только сделать 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 могут быть довольно сложными, хотя.

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

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

Ответ 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)))

и т.д.