Как ленивый?

Question

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

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

Как оценивается foldl:
1) Создана целая куча громов
2) после того, как Haskell завершил создание thunks, thunks уменьшены
3) переполнить стек, если слишком много thunks

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

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

---

ОБНОВЛЕНИЕ: похоже, что ответ на мой вопрос как-то связан с нормальной формой, слабой нормальной формой и нормальной головой, а также реализацией их Haskell.
Тем не менее, я все еще ищу пример, где оценка функции объединения более охотно привела бы к другому результату (либо сбой, либо ненужная оценка).

Answer 1

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

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

Answer 2

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

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 'заключается лишь в том, что приведенное выше выражение вынуждено вычислять в каждой рекурсии, поэтому в конце вы получите значение в нормальной форме со слабой головой.

Answer 3

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

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

См. Также: Real World Haskell> Функциональное программирование # Левые сгибы, лень и утечки пространства

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

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

1) Почему сокращениедолжно произойти после всех бросков?

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

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

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

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

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

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

См. Также: PLAI> Часть III: Лень

Answer 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