Есть ли промежуточная структура данных, созданная в списках

Question

Похоже, что foldr выполняет какое-то слияние со списком, поэтому требует меньше памяти (11 МБ) по сравнению с foldl (21 МБ) в этом примере, например,

myfunc = sum $ foldr g acc [ f x | x <- xs ]
f x = ..
g x y = ..

Может кто-нибудь объяснить, как и почему? Также, как ленивые оценки помогают в этом.

Answer 1

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

Правое сгибание может для соответствующих функций (таких, которые могут выдавать [частичный] результат без проверки второго аргумента) инкрементно генерировать свой результат, так что, если результат соответствующим образом используется и список входных данных генерируется соответствующим образом,все вычисления могут выполняться в небольшом постоянном пространстве.Как сказал sclv, в этих случаях он сводится в основном к циклу.

Answer 2

Мы можем обесценить понимание как, по сути, map f xs. Если вы компилируете это, тогда ghc действительно сможет объединить сумму, сгиб и карту в один проход: http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion. Но даже если вы этого не сделаете, лень - ваш друг для использования памяти , Список, составленный картой, является ленивым - f применяется только по требованию. И f будет требоваться только тогда, когда этого требует сворачивание А так как ваш фолд явно создает другой (ленивый) список, то каждый шаг фолда требует только сумма по очереди. Таким образом, вы по-прежнему применяете каждую функцию по очереди, но вам не нужно создавать полную промежуточную структуру данных одновременно. В то время как вы написали целый набор композиций функций, модель оценки будет склонна обрабатывать этот конкретный набор кода, по модулю целую кучу помахивания рукой, что-то вроде цикла (хотя, без слияния, цикл с достаточным количеством косвенности).

Answer 3

Это особенность компилятора GHC. По сути, GHC может распознать, когда список используется в «конвейере», и может преобразовать всю конструкцию в эквивалент while -петля в C, который вообще не выделяет список.

Причина, по которой это работает с foldr, а не foldl, зависит от функции g, которую вы используете в своем примере. Так как foldr, в отличие от foldl, накапливает результаты функции, заданной в качестве параметра (aka: foldl нужен весь список, прежде чем он сможет начать фактически оценивать функцию g, поэтому он создает огромный «поток» из неоцененных функций и конечный элемент списка в качестве своего результата - именно поэтому в этом случае он использует гораздо больше памяти - тогда как foldr может начать вычислять g, как только получает любой вход в список), он называется «строгим» в своем аккумуляторе, и компилятор может сделать некоторые предположения, которые могут привести к оптимизации.

Если, например, функция g возвращает значение, являющееся списком, она может продолжить вышеупомянутую стратегию оптимизации "конвейера", в основном трактуя foldr как map и делая всю конструкцию (из генерация списка для списочного потребления) в строгом цикле. Это возможно только потому, что foldr дает ровно один элемент списка для каждого потребляемого элемента списка, что не гарантируется для foldl (особенно для бесконечных списков).