Preguiça e recursão de cauda em Haskell, por que é isso funcionar?

Question

Eu tenho essa função bastante simples para calcular a média dos elementos de uma lista grande, usando dois acumuladores para segurar a soma até agora e a contagem até agora:

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]))

Agora, em uma linguagem rigorosa, isso seria cauda-recursivo, e não haveria nenhum problema. No entanto, como Haskell é preguiçoso, meu googling me levou a compreender que (s + x) e (l + 1) serão passadas a recursividade como thunks. Então, essa coisa toda cai e queima:

Stack space overflow: current size 8388608 bytes.

Depois de mais googling, eu encontrei seq e $!. Que parece que eu não entendo porque todas as minhas tentativas de usá-los neste contexto provou fútil, com mensagens de erro dizendo algo sobre tipos infinitos.

Finalmente eu encontrei -XBangPatterns, que resolve tudo, alterando a chamada recursiva:

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

Mas eu não estou feliz com isso, como -XBangPatterns é atualmente uma extensão. Eu gostaria de saber como fazer a avaliação rigorosa sem o uso de -XBangPatterns. (E talvez aprender algo também!)

Só para você entender a minha falta de compreensão, aqui está o que eu tentei (o único tento que compilado, que é):

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

Pelo que pude entender, seq deve aqui forçar a avaliação do argumento s e l, evitando assim o problema causado pelo thunks. Mas eu ainda obter um estouro de pilha.

Answer 1

Eu tenho escrito muito sobre isso:

• Real World Haskell, ch 24: controlar a avaliação do
• em recursão e rigor na Haskell

Em primeiro lugar, sim, se você quiser exigir avaliação rigorosa dos acumuladores usar seq e estadia em 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

Em segundo lugar: análise rigor vai chutar, se você dar algumas anotações de tipo, e compilar com -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

Porque 'Double' é um wrapper sobre o tipo atômica estrita Duplo #, com otimizações, e um tipo preciso, GHC corre análise rigor e infere que a versão estrita será ok.

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

Como descrito no capítulo RAC acima.

Answer 2

A avaliação forças função seq do primeiro parâmetro uma vez que a função é chamada. Quando você passar seq s (s+x) como parâmetro a função seq é não chamado imediatamente, porque não há necessidade de avaliar o valor desse parâmetro. Você quer que a chamada para seq a ser avaliado antes da chamada recursiva, para que que por sua vez pode forçar seu parâmetro a ser avaliado.

Geralmente isso é feito ligação com isto:

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

Esta é uma variação sintática de seq s (seq l (go (s+x) (l+1) xs)). Aqui as chamadas para seq são as chamadas de função ultraperiféricas na expressão. Por causa da preguiça de Haskell isso faz com que eles sejam avaliadas em primeiro lugar:. seq é chamado com os parâmetros ainda não avaliadas s e seq l (go (s+x) (l+1) xs), avaliando os parâmetros é adiada até o ponto em que alguém realmente tenta acessar seus valores

Agora seq pode forçar seu primeiro parâmetro a ser avaliado antes de retornar o resto da expressão. Em seguida, o próximo passo na avaliação seria a segunda seq. Se as chamadas para seq estão enterrados em algum lugar algum parâmetro não pode ser executado por um longo tempo, derrotando o seu propósito.

Com as posições alteradas dos seqs o executa programa finas, sem o uso de quantidades excessivas de memória.

Outra solução para o problema seria a de simplesmente permitir otimizações no GHC quando o programa é compilado (-O ou -O2). O otimizador reconhece a preguiça dispensável e produz código que não alocar memória desnecessária.

Answer 3

Você está certo em sua compreensão de que as forças seq s (s+x) a avaliação de s. Mas não forçar s+x, portanto, você ainda está construindo thunks.

Ao usar $! você pode forçar a avaliação da adição (duas vezes, nos dois argumentos). Isso atinge o mesmo efeito que usar os padrões de estrondo:

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

---

O uso da função $! irá traduzir o go $! (s+x) para o equivalente a:

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

Assim y é primeiramente forçados a forma normal cabeça fraca , o que significa que a função mais externa é aplicada. No caso de y, a função mais externa é +, assim y está totalmente avaliada para um número antes de ser passado para go.

---

Oh, e você provavelmente tem o tipo de mensagem de erro infinito porque você não tem o parêntese no lugar certo. Eu tenho o mesmo erro quando eu escrevi o seu primeiro programa para baixo: -)

Como o operador $! é associativos à direita, sem meios parêntese go $! (s+x) $! (l+1) o mesmo que:. go $! ((s+x) $! (l+1)), que é obviamente errado