Путаница в отношении лени

Question

у меня есть функция

myLength = foldl (\ x _ -> x + 1) 0

, который завершается с переполнением стека при вводе около 10 ^ 6 элементов (myLength [1..1000000] терпит неудачу). Я считаю, что это связано с наращиванием thunk, поскольку, когда я заменяю foldl на foldl ', это работает. Пока все хорошо.

Но теперь у меня есть другая функция, чтобы перевернуть список:

myReverse = foldl (\ acc x -> x : acc) []

, который использует ленивую версию foldl ( вместо of foldl ')

Когда я делаю myLength . myReverse $ [1..1000000]. На этот раз все работает отлично. Я не понимаю, почему foldl работает для более позднего случая, а не для первого?

Для пояснения здесь myLength использует foldl ', а myReverse использует foldl

Answer 1

Вот мое лучшее предположение, хотя я не эксперт по внутренним компонентам Haskell (пока).

При создании thunk Haskell распределяет все промежуточные переменные аккумулятора в куче 1004 *.

При выполнении сложения, как в myLength, необходимо использовать стек для промежуточных переменных. См. эту страницу . Выдержки:

Проблема начинается, когда мы наконец оцениваем z1000000:

Обратите внимание, что z1000000 = z999999 + 1000000. Таким образом, 1000000 помещается в стек. Затем z999999 оценивается.

Обратите внимание, что z999999 = z999998 + 999999. Таким образом, 999999 помещается в стек. затем z999998 оценивается:

Обратите внимание, что z999998 = z999997 + 999998. Таким образом, 999998 помещается в стек. затем z999997 оценивается:

Однако, когда я выполняю построение списка, я думаю, что вот что происходит (именно здесь начинается догадка):

При оценке z1000000:

Обратите внимание, что z1000000 = 1000000: z999999. Таким образом, 1000000 хранится внутри z1000000 вместе со ссылкой (указателем) до z999999. Затем оценивается z999999.

Обратите внимание, что z999999 = 999999: z999998. Таким образом, 999999 хранится внутри z999999, вместе со ссылкой на z999998. затем z999998 оценивается.

и т.д.

Обратите внимание, что изменение z999999, z999998 и т. Д. Из выражения, еще не оцененного в один элемент списка, является повседневной вещью в Haskell:)

Поскольку z1000000, z999999, z999998 и т. Д. Находятся в куче, эти операции не используют пространство стека. QED.