Последствия foldr vs foldl (или foldl ‘)

Во-первых, Real World Haskell , который я читаю, говорит, что никогда не используйте foldl и вместо этого используйте foldl' . Поэтому я верю.

Но я foldl' когда нужно использовать foldr vs. foldl' . Хотя я вижу структуру того, как они работают по-разному, передо мной, я слишком глуп, чтобы понять, когда «что лучше». Думаю, мне кажется, что это не имеет особого значения, потому что они оба дают один и тот же ответ (не так ли?). Фактически, мой предыдущий опыт работы с этой конструкцией – это reduce от Ruby и reduce Clojure, которые, похоже, не имеют «левых» и «правильных» версий. (Боковой вопрос: какую версию они используют?)

Любое понимание, которое может помочь умному, подобному мне виду, было бы очень оценено!

Рекурсия для foldr fx ys где ys = [y1,y2,...,yk] выглядит

 f y1 (f y2 (... (f yk x) ...)) 

тогда как recursion для foldl fx ys выглядит

 f (... (f (fx y1) y2) ...) yk 

Важным отличием здесь является то, что если результат вычисления fxy можно вычислить, используя только значение x , то foldr не «нужно исследовать весь список. Например

 foldr (&&) False (repeat False) 

возвращает False тогда как

 foldl (&&) False (repeat False) 

никогда не заканчивается. (Примечание: repeat False создает бесконечный список, где каждый элемент False .)

С другой стороны, foldl' является хвостом рекурсивным и строгим. Если вы знаете, что вам придется пересекать весь список независимо от того, что (например, суммируя числа в списке), то foldl' больше пространства (и, вероятно, времени), чем foldr .

foldr выглядит так:

Визуализация с правой стороны

foldl выглядит так:

Визуализация влево-влево

Контекст: Сложить на вики Haskell

Их семантика отличается тем, что вы не можете просто обменять foldl и foldr . Один складывает элементы слева, а другой справа. Таким образом, оператор применяется в другом порядке. Это имеет значение для всех неассоциативных операций, таких как вычитание.

У Haskell.org есть интересная статья по этому вопросу.

Вскоре foldr лучше, когда функция аккумулятора ленив по второму аргументу. Подробнее о переполнении стека Haskell wiki (каламбур).

Причина foldl' предпочтительнее foldl поскольку 99% всех применений состоит в том, что он может работать в постоянном пространстве для большинства применений.

Возьмем функцию sum = foldl['] (+) 0 . Когда используется foldl' , сумма немедленно вычисляется, поэтому применение sum к бесконечному списку будет выполняться вечно и, скорее всего, в постоянном пространстве (если вы используете такие вещи, как Int s, Double s, Float s. Integer s будет используйте больше, чем постоянное пространство, если число становится больше, чем maxBound :: Int ).

С foldl создается thunk (например, рецепт того, как получить ответ, который может быть оценен позже, вместо сохранения ответа). Эти thunks могут занимать много места, и в этом случае гораздо лучше оценить выражение, чем хранить thunk (приводя к переполнению стека … и приводя вас к … ох, неважно)

Надеюсь, это поможет.

Кстати, foldl Ruby и reduce Clojure – foldl (или foldl1 , в зависимости от того, какую версию вы используете). Обычно, когда в языке есть только одна форма, это левая складка, включая reduce Python, List::Util::reduce Perl List::Util::reduce , C ++, array_reduce C #, inject:into: Smalltalk inject:into: array_reduce PHP, Mathematica’s Fold и т. Д. Common Lisp reduce значения по умолчанию для левой складки, но есть опция для правой складки.

Как указывает Конрад , их семантика различна. У них нет одинакового типа:

 ghci> :t foldr foldr :: (a -> b -> b) -> b -> [a] -> b ghci> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a ghci> 

Например, оператор добавления списка (++) может быть реализован с помощью foldr as

 (++) = flip (foldr (:)) 

в то время как

 (++) = flip (foldl (:)) 

даст вам ошибку типа.

  • Объяснение «привязка узла»
  • Обработка инкрементного моделирования данных Изменения в функциональном программировании
  • Есть ли в Java SE 8 пары или кортежи?
  • какова хорошая постоянная структура коллекций для использования в java?
  • Есть ли способ сделать currying в C?
  • почему функции lambda в c ++ 11 не имеют функции типов?
  • Объединение двух списков в Haskell
  • Почему java.util.Collection не реализует новый интерфейс Stream?
  • Группировать путем подсчета в Java 8 stream API
  • В чем разница между lapply и do.call?
  • Функциональное программирование на Java
  • Interesting Posts

    Могу ли я решить эту проблему с помощью чистого mysql? (присоединение к ‘;’ разделенные значения в столбце)

    Нажатие Rails с SQLite3 на Heroku не удается

    Вычислить разницу даты и времени в Excel

    Объединение n DataTables в единую таблицу данных

    Как я могу получить снимок веб-сайта, который может служить доказательством его текущего состояния?

    Как получить и переустановить Windows XP

    Отправка формы сервлету, который взаимодействует с базой данных, приводит к пустой странице

    Принудительное приложение iphone для программной перезагрузки

    Уровни DAO и Service (JPA / Hibernate + Spring)

    Как я могу заставить несколько видеокарт работать в Linux?

    Получение ошибки сертификата в IE и Chrome, но открывается в FireFox

    Почему вызов функции требует имя параметра в Swift?

    Как сохранить объект в базе данных sqlite?

    Первичные файлы FileUpload с PrettyFaces и JSF 2.2.3

    Есть ли функция Notepad ++ для добавления некоторого вертикального пространства в нижнюю часть или прокрутка ниже последней строки?

    Давайте будем гением компьютера.