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

Я изучаю 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

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

Ответ 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' делает, просто избегает создания thunk: 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)

Это позволяет избежать трюков вообще.

Ответ 2

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

Как объясняется здесь, оценка WHNF останавливается после каждого применения конструктора . (a, b) поэтому всегда находится в WHNF, даже если a и 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]