Как складывается ленивый?

В Haskell есть много хороших вопросов и ответов о foldl, foldr и foldl'.

Итак, теперь я знаю это:
1) foldl - ленивый
2) не используйте foldl, потому что он может взорвать стек
3) используйте foldl' вместо этого, потому что это строго (ish)

Как оценивается foldl:
1) создается целая куча тромбов

2) после того, как Haskell закончил создавать трюки, уменьшаются громкости
3) переполнение стека, если слишком много thunks

Что меня смущает:
1) почему происходит редукция после всех торможений?
2) почему не foldl оценивается так же, как foldl'? Это просто побочный эффект реализации?
3) из определения , foldl выглядит так, что его можно эффективно оценить с помощью tail-recursion - как я могу определить, будет ли функция фактически быть эффективно оценены? Кажется, что я должен начать беспокоиться о порядке оценки в Haskell, если я не хочу, чтобы моя программа потерпела крах.

Спасибо заранее. Я не знаю, правильно ли я понимаю оценку foldl. При необходимости предложите исправления.

UPDATE: похоже, что ответ на мой вопрос имеет отношение к Нормальной форме, Слабой нормальной форме и Head Normal Form, а также к реализации Haskell из них.
Тем не менее, я все еще ищу пример, где более высокая оценка функции объединения приведет к другому результату (либо к сбою, либо к ненужной оценке).

Ответ 1

Вы знаете, что по определению:

foldl op start (x1:x2:...:xN:[]) = ((start `op` x1) `op` x2) ...

строка в foldl, которая делает это:

foldl op a (x:xs) = foldl op (a `op` x) xs

Вы правы, что это хвост рекурсивный, но обратите внимание, что выражение

(a `op` x)

ленив, и в конце списка будет создано огромное выражение, которое затем будет уменьшено. Разница в foldl 'заключается в том, что выражение, указанное выше, вынуждено оценивать в каждой рекурсии, поэтому в конце вы имеете значение в слабой форме головы.

Ответ 2

Короткий ответ заключается в том, что в foldl f это не обязательно тот случай, когда f является строгим, поэтому может быть слишком жарко, чтобы уменьшить громкость фронта. Однако на практике это обычно так, поэтому вы почти всегда хотите использовать foldl'.

Я написал более подробное объяснение того, как порядок оценки foldl и foldl' работает по другому вопросу. Это довольно долго, но я думаю, что это должно немного разъяснить вам кое-что.

Ответ 3

Я все еще ищу пример, где более высокая оценка функции объединения приведет к другому результату

Общее эмпирическое правило никогда, никогда не используется foldl. Всегда используйте foldl', , за исключением случаев, когда вы должны использовать foldr. Я думаю, вы знаете достаточно о foldl, чтобы понять, почему этого следует избегать.

Однако ваш вопрос пренебрегает foldr. Отличительной особенностью foldr является то, что он может создавать дополнительные результаты, а foldl' должен пройти весь список до получения ответа. Это означает, что foldr лень позволяет ему работать с бесконечными списками. Есть также вопросы и ответы, которые подробно рассказывают об этом.

Подняв это, позвольте мне попытаться кратко ответить на ваши вопросы.

1), почему происходит редукция после всех торможений?

Сокращение происходит только в точках строгости. Например, выполнение ввода-вывода является строгостью. foldl' использует seq для добавления дополнительной точки строгости, которая не имеет foldl.

2) почему не foldl оценивается так же, как foldl '? Это просто побочный эффект реализации?

Из-за дополнительной точки строгости в foldl'

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

Вам нужно узнать немного больше о ленивой оценке. Ленивая оценка не является исключительной для Haskell, но Haskell является одним из самых, очень немногих языков, на которых лень является дефолтом. Для новичков просто помните, что всегда используйте foldl', и все должно быть в порядке.

Если ленивость на самом деле заставит вас когда-нибудь попасть в неприятности, то вам, вероятно, следует убедиться, что вы понимаете лень и строгость Хаскелла. Вы можете сказать, что теоретический день - это строгость для обучения по принципу "ленивый по умолчанию".

Смотрите также: PLAI > Часть III: Лень

Ответ 4

Кажется, что я должен начать беспокоиться о порядке оценки в Haskell, если я не хочу, чтобы моя программа потерпела крах.

На мой взгляд, лучшие варианты, если вы хотите, чтобы ваша программа не сработала, (оценивается с худшего с точки зрения урожайности за потраченное усилие): 1. Дайте ему достаточно ресурсов. 2. Улучшите свой алгоритм. 3. Сделайте микрооптимизации (одна из которых foldl').

Итак, скорее, если вы беспокоитесь о порядке оценки, я предпочел бы сначала подумать о том, что нужно оценивать (достаточно foldr?), если я вообще не сделаю этого?). И до этого я бы увеличил доступное пространство стека.

Вы не ограничиваете свою всю программу до 8 МБ ОЗУ, не так ли? Почему бы вам ограничить пространство стека? Просто увеличьте пространство стека до 4 ГБ и начните беспокоиться, когда что-то действительно сильно его завораживает (например, с кучей памяти).

И несколько ответить на вопрос о том, как foldl ленив:

foldl (\x y -> y) undefined [undefined, 8] -- evaluates to 8
foldl' (\x y -> y) undefined [undefined, 8] -- fails to evaluate