Подтвердить что ты не робот

Лень и хвост рекурсии в Haskell, почему это грохот?

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

mean = go 0 0
    where
      go s l []     = s / fromIntegral l
      go s l (x:xs) = go (s+x) (l+1) xs

main = do
  putStrLn (show (mean [0..10000000]))

Теперь, на строгом языке, это будет хвост-рекурсивным, и проблем не будет. Однако, поскольку Haskell ленив, мой поисковик привел меня к пониманию того, что (s + x) и (l + 1) будут переданы по рекурсии в виде thunks. Таким образом, все это сбой и ожоги:

Stack space overflow: current size 8388608 bytes.

После дальнейшего поиска в Google я нашел seq и $!. Кажется, что я не понимаю, потому что все мои попытки использовать их в этом контексте оказались бесполезными, а сообщения об ошибках говорили о бесконечных типах.

Наконец, я нашел -XBangPatterns, который решает все это путем изменения рекурсивного вызова:

go !s !l (x:xs) = go (s+x) (l+1) xs

Но я не доволен этим, так как -XBangPatterns в настоящее время является расширением. Я хотел бы знать, как сделать оценку строгой без использования -XBangPatterns. (И, может быть, тоже научитесь!)

Просто, чтобы вы поняли мое отсутствие понимания, вот что я пробовал (единственная попытка скомпилировать, то есть):

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs

Из того, что я мог понять, seq должен здесь заставить оценивать аргументы s и l, тем самым избегая проблемы, вызванной thunks. Но я все равно получаю переполнение стека.

4b9b3361

ОТВЕТЫ

Ответ 1

Я подробно писал об этом:

Во-первых, да, если вы хотите потребовать строгой оценки аккумуляторов, используйте seq и оставайтесь в Haskell 98:

mean = go 0 0
  where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = s `seq` l `seq`
                      go (s+x) (l+1) xs

main = print $ mean [0..10000000]

*Main> main
5000000.0

Во-вторых: анализ строгости начнется, если вы дадите аннотации некоторого типа и скомпилируйте с помощью -O2:

mean :: [Double] -> Double
mean = go 0 0
 where
  go :: Double -> Int -> [Double] -> Double
  go s l []     = s / fromIntegral l
  go s l (x:xs) = go (s+x) (l+1) xs

main = print $ mean [0..10000000]

$ ghc -O2 --make A.hs
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.0
./A  0.46s user 0.01s system 99% cpu 0.470 total

Потому что "Двойной" является оболочкой над строгим атомным типом Double #, с оптимизацией и точным типом, GHC проводит анализ строгости и сообщает, что строгая версия будет в порядке.

import Data.Array.Vector

main = print (mean (enumFromToFracU 1 10000000))

data Pair = Pair !Int !Double

mean :: UArr Double -> Double   
mean xs = s / fromIntegral n
  where
    Pair n s       = foldlU k (Pair 0 0) xs
    k (Pair n s) x = Pair (n+1) (s+x)

$ ghc -O2 --make A.hs -funbox-strict-fields
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.5
./A  0.03s user 0.00s system 96% cpu 0.038 total

Как описано в главе RWH выше.

Ответ 2

Функция seq принудительно оценивает первый параметр после вызова функции. Когда вы передаете seq s (s+x) в качестве параметра, функция seq не вызывается немедленно, потому что нет необходимости оценивать значение этого параметра. Вы хотите, чтобы вызов seq оценивался до рекурсивного вызова, так что это, в свою очередь, может заставить его параметр быть оцененным.

Обычно это делается ссылкой:

 go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs

Это синтаксическая вариация seq s (seq l (go (s+x) (l+1) xs)). Здесь вызовы seq являются внешними вызовами функций в выражении. Из-за лени Haskell это заставляет их сначала оценивать: seq вызывается с еще невыплаченными параметрами s и seq l (go (s+x) (l+1) xs), оценка параметров откладывается до точки, где кто-то действительно пытается получить доступ к своим значениям.

Теперь seq может заставить свой первый параметр быть оценен перед возвратом остальной части выражения. Тогда следующим шагом в оценке будет второй seq. Если вызовы на seq где-то захоронены каким-то параметром, они могут не выполняться в течение длительного времени, превзойдя их цель.

С измененными позициями seq программа выполняет штраф, не используя чрезмерные объемы памяти.

Другим решением проблемы было бы просто включить оптимизацию в GHC при компиляции программы (-O или -O2). Оптимизатор распознает неприемлемую лень и создает код, который не выделяет ненужную память.

Ответ 3

Вы правы в своем понимании, что seq s (s+x) заставляет оценивать s. Но он не заставляет s+x, поэтому вы все еще создаете громкие трюки.

Используя $!, вы можете принудительно выполнить оценку добавления (два раза для обоих аргументов). Это обеспечивает тот же эффект, что и при использовании шаблонов взлома:

mean = go 0 0
 where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = ((go $! s+x) $! l+1) xs

Использование функции $! приведет к переводу go $! (s+x) в эквивалент:

let y = s+x 
in seq y (go y)

Таким образом, y сначала принудительно переходит в слабую гласную нормальную форму, что означает, что применяется внешняя функция. В случае y самая внешняя функция +, поэтому y полностью вычисляется до числа перед передачей в go.

О, и вы, вероятно, получили сообщение об ошибке бесконечного типа, потому что у вас не было круглых скобок в нужном месте. У меня такая же ошибка, когда я впервые написал вашу программу: -)

Поскольку оператор $! является правильным ассоциативным, без круглой скобки go $! (s+x) $! (l+1) означает то же самое, что: go $! ((s+x) $! (l+1)), что, очевидно, неверно.