Лень и хвостовая рекурсия в Хаскеле, почему это терпит крах? - PullRequest
Новая
       38

Лень и хвостовая рекурсия в Хаскеле, почему это терпит крах?

18 голосов
/ 24 октября 2009

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

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) будут передаваться по рекурсии как thunk. Таким образом, все это терпит крах и горит: 

Stack space overflow: current size 8388608 bytes.

После дальнейшего поиска, я нашел 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. Но я все еще получаю переполнение стека.

Ответы [ 3 ]

25 голосов
/ 24 октября 2009

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

Во-первых, да, если вы хотите требовать строгой оценки аккумуляторов, используйте 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 является оберткой над строгим атомарным типом 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 выше.

9 голосов
/ 25 октября 2009

Функция 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 являются самыми внешними вызовами функций в выражении. Из-за лени Хаскелла это приводит к тому, что они сначала оцениваются: seq вызывается с еще не оцененными параметрами s и seq l (go (s+x) (l+1) xs), оценка параметров откладывается до точки, где кто-то фактически пытается получить доступ к их значениям.

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

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

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

6 голосов
/ 24 октября 2009

Вы правы в том понимании, что 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)), что, очевидно, неверно.

...