Беспорядок относительно лени
У меня есть функция
myLength = foldl (\ x _ -> x + 1) 0
который перестал работать с переполнением стека с входом вокруг 10^6 элементы (myLength [1.. 1000000] сбои). Я полагаю, что это происходит из-за преобразователя, растут с тех пор, когда я заменяю foldl foldl', он работает.Пока все хорошо.
Но теперь у меня есть другая функция для инвертирования списка:
myReverse = foldl (\ acc x -> x : acc) []
который использует ленивую версию foldl (вместо foldl')
Когда я делаю myLength . myReverse $ [1..1000000]. На этот раз это хорошо работает. Мне не удается понять, почему foldl работает на более поздний случай а не на формирователь?
Разъясниться здесь myLength использует foldl', в то время как myReverse использует foldl
1 ответ
Вот мое лучшее предположение, хотя я не эксперт по внутреннему устройству Haskell (пока).
При построении преобразователя Haskell размещает все промежуточные переменные аккумулятора в куче .
При выполнении сложения, как в 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.