Путаница относительно лени

Question

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

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

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

Но теперь у меня есть еще одна функция, чтобы полностью изменить список:

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

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

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

Для уточнения здесь myLength использует foldl»в то время как myReverse использует foldl

Answer 1

Вот моя догадка, хотя я не специалист по Haskell внутренностей (пока).

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

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

Проблема начинается тогда, когда мы, наконец, оценить 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.