Почему моя интуиция о самореференциальных ленивых последовательностях неверна?

В Haskell я могу написать самореляционную последовательность в GHCI, например:

λ> let x = 1:map (+1) x
λ> take 5 x

который производит:

[1,2,3,4,5]

Однако моя интуиция относительно ленивой оценки говорит, что это должно произойти во время расширения

let x = 1:map (+1) x
1:2:map (+1) x
1:2:map (+1) [1, 2] <-- substitution
1:2:2:3:map (+1) x
1:2:2:3:map (+1) [1, 2, 2, 3] <-- substitution
1:2:2:3:2:3:3:4:map (+1) x
...

Это явно не то, что происходит. Я вижу шаблон в правильном ответе. Мы просто перемещаем один элемент в списке за раз в бесконечный поток. Я признаю шаблон, и я могу применить его в коде. Однако это не соответствует моей ментальной модели ленивой оценки. Он чувствует себя немного "волшебным". Где моя интуиция ошибается?

Ответы

Ответ 1

Помните только, чтобы заменить что-то своим определением. Поэтому всякий раз, когда вы расширяете x, вы должны подставить 1 : map (+1) x, а не его "текущее значение" (что бы это ни значило).

Я воспроизведу идею Джефффри, но с должным уважением к лени.

x = 1 : map (+1) x

take 5 x
= take 5 (1 : map (+1) x)                                 -- x
= 1 : take 4 (map (+1) x)                                 -- take
= 1 : take 4 (map (+1) (1 : map (+1) x)                   -- x
= 1 : take 4 (2 : map (+1) (map (+1) x))                  -- map and (+)
= 1 : 2 : take 3 (map (+1) (map (+1) x))                  -- take
= 1 : 2 : take 3 (map (+1) (map (+1) (1 : map (+1) x)))   -- x
= 1 : 2 : take 3 (map (+1) (2 : map (+1) (map (+1) x)))   -- map and (+)
= 1 : 2 : take 3 (3 : map (+1) (map (+1) (map (+1) x)))   -- map and (+)
= 1 : 2 : 3 : take 2 (map (+1) (map (+1) (map (+1) x)))   -- take

и т.д.

Упражнение завершает оценку в этом стиле самостоятельно (это довольно информативно).

Обратите внимание, как мы начинаем наращивать цепочку map по мере роста списка. Если вы просто print x, через некоторое время вы увидите, что начало запуска замедляется; вот почему. Существует более эффективный способ, оставленный как упражнение (и [1..] изменяет: -).

N.B. это все еще немного менее лениво, чем то, что на самом деле произойдет. map (+1) (1 : ...) оценивается как (1+1) : map (+1) ..., и добавление произойдет только тогда, когда число действительно наблюдается, либо путем его печати, либо, например, сравнивая его.

Уилл Несс указал на ошибку в этом сообщении; см. комментарии и его ответ.

Ответ 2

Вот что происходит. Лень - это нестрогость + мемонирование (thunks). Мы можем показать это, назвав все временные данные, которые возникают, когда выражение принудительно:

λ> let x  = 1  : map (+1) x
   >>> x  = a1 : x1                             -- naming the subexpressions
       a1 = 1
       x1 = map (+1) x 

λ> take 5 x 
==> take 5 (a1:x1)                              -- definition of x
==> a1:take 4 x1                                -- definition of take
          >>> x1 = map (1+) (1:x1)              -- definition of x
                 = (1+) 1 : map (1+) x1         -- definition of map
                 = a2     : x2                  -- naming the subexpressions
              a2 = (1+) 1                        
              x2 = map (1+) x1  
==> a1:take 4 (a2:x2)                           -- definition of x1
==> a1:a2:take 3 x2                             -- definition of take
             >>> x2 = map (1+) (a2:x2)          -- definition of x1
                    = (1+) a2 : map (1+) x2     -- definition of map
                    = a3      : x3              -- naming the subexpressions
                 a3 = (1+) a2                    
                 x3 = map (1+) x2  
==> a1:a2:take 3 (a3:x3)                        -- definition of x2
==> a1:a2:a3:take 2 x3                          -- definition of take
                >>> x3 = map (1+) (a3:x3)       -- definition of x2
.....

Элементы в результирующем потоке a1:a2:a3:a4:... относятся к своему предшественнику: a1 = 1; a2 = (1+) a1; a3 = (1+) a2; a4 = (1+) a3; ....

Таким образом, это эквивалентно x = iterate (1+) 1. Без совместного использования данных и их повторного использования через обратную ссылку (включенную с помощью memoization storage) она будет эквивалентна x = [sum $ replicate n 1 | n <- [1..]], которая является радикально менее эффективным вычислением (O (n ²)) вместо O (n)).

Мы можем объяснить совместное использование без разделения с помощью

fix g = x where x = g x        -- sharing fixpoint
x = fix ((1:) . map (1+))      --  corecursive definition

_Y g = g (_Y g)                -- non-sharing fixpoint
y = _Y ((1:) . map (1+))       --  recursive definition

Попытка распечатать y в приглашении GHCi показывает заметное замедление по мере продвижения. Там нет замедления при печати потока x.

(см. также fooobar.com/questions/5304/... для аналогичного примера).

Ответ 3

Вы сопоставляете +1 по всему списку, так что начальный 1 становится n, где n - это количество раз, когда вы лениво рекурсируете, если это имеет смысл. Поэтому вместо вывода, о котором вы думаете, это выглядит более похоже:

1:...                            -- [1 ...]
1: map (+1) (1:...)              -- [1, 2 ...]
1: map (+1) (1:map (+1) (1:...)) -- [1, 2, 3 ...]

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

Итак, вы можете подумать о n -ом шаге рекурсии, взяв список [1, 2, 3, ..., n ...], превратив его в список [2, 3, 4, ..., n+1 ...] и добавив 1.

Ответ 4

Давайте посмотрим на это немного математически. Предположим, что

x = [1, 2, 3, 4, ...]

Тогда

map (+1) x = [2, 3, 4, 5, ...]

так

1 : map (+1) x = 1 : [2, 3, 4, 5, ...] = x

Это (повернутое) - это уравнение, с которого мы начали:

x = 1 : map (+1) x

Итак, мы показали, что

x = [1, 2, 3, 4, ...]

- решение уравнения

x = 1 : map (+1) x   -- Eqn 1

Следующий вопрос, конечно, заключается в том, есть ли какие-либо другие решения для уравнения 1. Ответ, как оказалось, - нет. Это важно, потому что модель оценки Haskell эффективно выбирает "наименее определенное" решение любого такого уравнения. Например, если бы мы определили x = 1 : tail x, то любой список, начинающийся с 1, был бы решением, но мы фактически получили бы 1 : _|_, где _|_ представляет ошибку или не прерывание. Уравнение 1 не приводит к такому беспорядку:

Пусть y - любое решение уравнения 1, поэтому

y = 1 : map (+1) y

Заметим, что из определения можно сказать, что

take 1 y = [1] = take 1 x

Предположим теперь, что

take n y = take n x

Тогда

take (n+1) y = take (n+1) (1 : map (+1) y)
             = 1 : take n (map (+1) y)
             = 1 : map (+1) (take n y)
             = 1 : map (+1) (take n x)
             = 1 : take n (map (+1) x)
             = take (n+1) (1 : map (+1) x)
             = take (n+1) x

По индукции получаем, что take n y = take n x для каждого n. То есть y = x.

Ответ 5

Что вы ошибаетесь

В вашем порядке оценки:

let x = 1:map (+1) x
1:2:map (+1) x
1:2:map (+1) [1, 2] <-- here

вы делаете неправильное предположение. Вы принимаете x is [1, 2], потому что количество элементов, которые вы можете увидеть там. Не это. Вы забыли подумать, что x в конце нужно вычислить рекурсивно.

Фактический поток

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

take 5 $ 1:map (+1) ...
take 5 $ 1:map (+1) (1:map (+1) ...
take 5 $ 1:map (+1) (1:map (+1) (1:map (+1) ...
take 5 $ 1:map (+1) (1:map (+1) (1:map (+1) (1:map (+1) ...
take 5 $ 1:map (+1) (1:map (+1) (1:map (+1) (1:map (+1) (1:map (+1) ...
take 5 $ 1:map (+1) (1:map (+1) (1:map (+1) (1:map (+1) [1 ...
take 5 $ 1:map (+1) (1:map (+1) (1:map (+1) [1, 2 ...
take 5 $ 1:map (+1) (1:map (+1) [1, 2, 3 ...
take 5 $ 1:map (+1) [1, 2, 3, 4 ...
take 5 $ [1, 2, 3, 4, 5 ...
[1, 2, 3, 4, 5]