Ленькая оценка терминов в бесконечном списке в Haskell

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

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

Это создаст бесконечный список последовательности фибоначчи.

Мой вопрос в том, что если я сделаю следующее:

takeWhile (<5) fibs

сколько раз fibs оценивать каждый термин в списке? Кажется что, поскольку takeWhile проверяет функцию предиката для каждого элемента в список, список fibs будет оценивать каждый термин несколько раз. первые 2 условия даются бесплатно. Когда takeWhile хочет оценить (<5) на 3-м элементе, мы получим:

1 : 1 : zipWith (+) [(1, 1), (1)] => 1 : 1 : 3

Теперь, когда takeWhile хочет оценить (<5) для 4-го элемента: рекурсивный характер fibs будет строить список снова, как следующее:

1 : 1 : zipWith (+) [(1, 2), (2, 3)] => 1 : 1 : 3 : 5

Казалось бы, третий элемент нужно снова вычислить, когда мы хотите оценить значение 4-го элемента. Кроме того, если предикат в takeWhile велик, это указывает на то, что функция делать больше работы, которая необходима, поскольку она оценивает каждый предыдущий элемент в списке несколько раз. Является ли мой анализ здесь правильным или Haskell делает некоторое кэширование для предотвращения множественных оценок здесь?

Ответ 1

Это самореферентная, ленивая структура данных, где "более поздние" части структуры относятся к более ранним частям по имени.

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

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

> take 2 fibs

(указатель на ячейку cons, указывающий на "1", и хвост, удерживающий второй "1", и указатель на функцию, которая возвращает ссылки на фибры, и хвост фиб.

Оценка еще одного шага расширяет структуру и скользит ссылки вдоль:

Итак, мы разворачиваем структуру, каждый раз принося новый неоцененный хвост, который является замыканием, удерживающим ссылки на 1-й и 2-й элементы последнего шага. Этот процесс может продолжаться бесконечно:)

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

Ответ 2

Иллюстрация:

module TraceFibs where

import Debug.Trace

fibs :: [Integer]
fibs = 0 : 1 : zipWith tadd fibs (tail fibs)
  where
    tadd x y = let s = x+y
               in trace ("Adding " ++ show x ++ " and " ++ show y
                                   ++ "to obtain " ++ show s)
                        s

Что производит

*TraceFibs> fibs !! 5
Adding 0 and 1 to obtain 1
Adding 1 and 1 to obtain 2
Adding 1 and 2 to obtain 3
Adding 2 and 3 to obtain 5
5
*TraceFibs> fibs !! 5
5
*TraceFibs> fibs !! 6
Adding 3 and 5 to obtain 8
8
*TraceFibs> fibs !! 16
Adding 5 and 8 to obtain 13
Adding 8 and 13 to obtain 21
Adding 13 and 21 to obtain 34
Adding 21 and 34 to obtain 55
Adding 34 and 55 to obtain 89
Adding 55 and 89 to obtain 144
Adding 89 and 144 to obtain 233
Adding 144 and 233 to obtain 377
Adding 233 and 377 to obtain 610
Adding 377 and 610 to obtain 987
987
*TraceFibs>

Ответ 3

Когда что-то оценивается в Haskell, оно остается оцениваемым, если оно ссылается на одно и то же имя ¹.

В следующем коде список l оценивается только один раз (что может быть очевидным):

let l = [1..10]
print l
print l -- None of the elements of the list are recomputed

Даже если что-то частично оценивается, эта часть остается оцененной:

let l = [1..10]
print $ take 5 l -- Evaluates l to [1, 2, 3, 4, 5, _]
print l          -- 1 to 5 is already evaluated; only evaluates 6..10

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

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

Ответ 4

Подумайте об этом так. Переменная fib является указателем на ленивое значение. (Вы можете думать о ленивом значении ниже как структура данных, например (не настоящий синтаксис) Lazy a = IORef (Unevaluated (IO a) | Evaluated a), т.е. Она начинается как неоцениваемая с помощью thunk, а затем, когда она оценивается, она "изменяется" на то, что запоминает значение.) Поскольку рекурсивное выражение использует переменную fib, у них есть указатель на одно и то же ленивое значение (они "разделяют" структуру данных). В первый раз, когда кто-то оценивает fib, он запускает thunk для получения значения, и это значение запоминается. И поскольку рекурсивное выражение указывает на одну и ту же ленивую структуру данных, когда они ее оценивают, они уже увидят оцененное значение. Когда они пересекают ленивый "бесконечный список", в памяти будет только один "частичный список"; zipWith будет иметь два указателя на "списки", которые просто указывают на предыдущих членов одного и того же "списка" из-за того, что он начинался с указателей в один и тот же список.

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

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