Сгибание Хаскелла / л и уменьшение Clojure

Question

Я решил серьезно отнестись к Haskell, и оборачиваюсь вокруг использования foldl и foldr .Они действительно очень похожи на сокращение Clojure - но я могу ошибаться и вскоре столкнулся с проблемой, которую, я надеюсь, кто-то легко объяснит.

Работа с этим документом: https://wiki.haskell.org/Foldr_Foldl_Foldl'

Прежде чем углубиться в реализацию моих собственных версий foldr / foldl, я решил сначала протестировать существующие из Prelude:

± |master U:2 ✗| → ghci
GHCi, version 8.6.3: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /Users/akarpov/.ghc/ghci.conf
Prelude> foldr (+) 0 [1..9999999]
49999995000000
Prelude> foldr (+) 0 [1..99999999]
*** Exception: stack overflow

Не ожидал этого (тот же результатпри использовании foldl);Я скорее ожидал что-то вроде Clojure:

> (time (reduce +' (range 1 99999999)))
"Elapsed time: 3435.638258 msecs"
4999999850000001

Единственное очевидное (и не относящееся к делу) различие заключается в использовании + 'вместо +, но это только для приспособления к системе типов JVM - число, производимое не't вписывается в [по умолчанию] Long, и + 'автоматически использует BigInteger, когда это необходимо.Самое главное, без переполнения стека.Похоже, что это указывает на то, что сворачивание / уменьшение в Haskell / Clojure реализовано совсем по-другому, или мое использование реализации haskell неверно.

в случае необходимости, это настройки глобального проекта:пакеты: [] - распознаватель: lts-13.8

Answer 1

Проблема

Как объясняет вики , функция (+) является строгой в обоих аргументах, что означает, что когда вы пытаетесь выполнить 1 + (2 + 3), вам сначала нужно вычислить(2 + 3).Хотя поначалу это может показаться не такой уж большой проблемой, это происходит, когда у вас длинный список.Цитируя вики,

для оценки: 1 + (2 + (3 + (4 + (...)))), в стек помещается 1.

Затем: 2 + (3 + (4 + (...))) оценивается.Таким образом, 2 помещается в стек.

Затем: 3 + (4 + (...)) оценивается.Таким образом, в стек помещается значение 3.

Затем: 4 + (...) оценивается.Таким образом, в стек помещается значение 4.

Затем: ваш ограниченный стек в конечном итоге заполнится, когда вы оцените достаточно большую цепочку (+) с.Затем это вызывает исключение переполнения стека.

Я не очень много о Clojure, но если (+') работает, то ему определенно не нужны оба аргумента для оценки перед уменьшением, и этоэто также решение в Haskell.

Решение

Foldl не решит проблему, так как известно, что foldl должен дважды пройти весь список, прежде чем возвращать результат - что неэффективно-, и даже тогда (+) остается строгим, поэтому приводимые выражения не сокращаются.

Чтобы решить эту проблему, вы должны использовать нестрогую функцию.В стандартной Prelude, seq :: a -> b -> b может использоваться именно для этого, и вот как foldl' работает.

Снова цитируя вики,

foldr - не только правильный сгибКроме того, обычно является правильным сгибом для использования , в частности, при преобразовании списков (или других складываемых объектов) в списки со связанными элементами в том же порядке.В частности, foldr будет эффективен для преобразования даже бесконечных списков в другие бесконечные списки.Для таких целей это должен быть ваш первый и самый естественный выбор.Например, обратите внимание, что foldr (:) [] == id.

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