Лень и хвостовая рекурсия в Haskell, почему это приводит к сбою?

Question

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

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 ленив, мой поиск в Google привел меня к пониманию того, что (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.Но я все равно получаю переполнение стека.

Answer 1

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

• Реальный мир Хаскелла, глава 24:контролирующая оценка
• О рекурсии и строгости в Haskell

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

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

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

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

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

Answer 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)) , что явно неверно.