Почему этот код не является постоянным?

Question

Я изучаю Haskell в настоящее время (будучи программистом по профессии, но это моя первая попытка функционального языка).

Я хочу написать функцию, которая сканирует список и возвращает как минимальный, так и максимальный элемент этого списка. В зависимости от того, что делают функции Prelude minimum и maximum, но оба они одновременно. Я придумал следующий код:

import Data.List 

-- Declaration of rand 

minMax :: [Int] -> Maybe (Int, Int) 
minMax [] = Nothing 
minMax (x:xs) = Just (foldl' f (x, x) xs) 
       where 
        f (a, b) c = (if c < a then c else a, if c > b then c else b) 

rand это функция, которая порождает бесконечный список чисел. Дело в том, что, когда я добавляю следующую main функцию:

main = print $ minMax $ take 1000000 $ rand 7666532 

компилировать и запускать все это с профилированием, он показывает мне, она использует более 200 Мб оперативной памяти, так что это определенно не является функцией постоянного пространства (которое Я бы хотел, чтобы это было).

Вопрос в том, почему и что я должен изменить, чтобы исправить это. Как я понимаю, foldl' складывает список слева (так же, как он создан) и не ленится, поэтому я не понимаю, почему использование памяти настолько велико. Я уверен, что это minMax функция, неверно, так как просто печать указанного списка, используя

main = print $ take 1000000 $ rand 7666532 

дает мне использование 1Мб, то, что я понимаю и ожидать.

Answer 1

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

Если вы явно заставить эти два элемента, вы получите постоянного пространства функции:

f (a, b) c = a `seq` b `seq` (if c < a then c else a, if c > b then c else b) 

В исходной программе вы строите кортеж вида: (<thunk>, <thunk>) и каждый раз f прикладывается вы просто построить кортеж с большими и большими трясинами. Когда, наконец, это поглощается print, вызов show заставляет полностью оценить кортеж, и все сравнения выполняются в этой точке.

Используя seq, вы вынуждаете f оценивать сравнение в этот момент, и, таким образом, перед выполнением сравнения оцениваются громкоговорители, содержащиеся в аккумуляторе. Следовательно, результат заключается в том, что громкость, хранящаяся в аккумуляторе, имеет постоянный размер.

Что такое foldl', просто избегайте строительства куска: f (f (f ...) y) x.

Альтернативное решение, как это было предложено Jubobs, чтобы избежать явного использования seq является использование типа данных, который имеет строгие поля:

data Pair a b = Pair !a !b 
    deriving Show 

И поэтому код станет:

minMax :: [Int] -> Maybe (Pair Int Int) 
minMax [] = Nothing 
minMax (x:xs) = Just (foldl' f (Pair x x) xs) 
       where 
        f (Pair a b) c = Pair (if c < a then c else a) (if c > b then c else b) 

Это позволяет избежать толчков в целом.

Answer 2

Функция seq, которая используется в foldl', по существу, заставляет ее первый аргумент оцениваться до WHNF (нормальная форма слабой головки).

Как объяснено here, оценка WHNF останавливается после каждого применения конструктора. Таким образом, (a, b) всегда находится в WHNF, даже если и b являются thunks, так как вы нажимаете на конструктор Tuple (,) перед тем, как добраться до a и b.

В результате, это пространство утечки, несмотря на использование foldl':

foldl' (\ (a, b) x -> (a + x, b + x)) (0, 1) [1..1000000] 

, но это не делает:

foldl' (\ (a, b) x -> a `seq` b `seq` (a + x, b + x)) (0, 1) [1..10000000] 

Это иногда удобно использовать расширение -XBangPatterns написать это:

foldl' (\ (!a, !b) x -> (a + x, b + x)) (0, 1) [1..10000000]