Acumuladores em haskell - haskell, recursão da cauda

Em Haskell, se eu escrever

 fac n = facRec n 1
where facRec 0 acc = acc
facRec n acc = facRec (n-1) (acc*n)

e compilá-lo com o GHC, o resultado será diferente do que se eu usasse

 fac 0 = 1
fac n = n * fac (n-1)

Eu poderia facilmente fazer fac n = product [1..n] e evitar a coisa toda, mas estou interessado emcomo uma tentativa de recursão da cauda funciona em uma linguagem preguiçosa. Entendo que ainda posso obter um estouro de pilha porque os thunks estão se acumulando, mas algo realmente acontece de maneira diferente (em termos do programa compilado resultante) quando eu uso um acumulador do que quando apenas declaro a recursão ingênua? Existe algum benefício em deixar de fora a recursão da cauda além da legibilidade aprimorada? A resposta muda mesmo se eu estiver usando runhaskell executar o cálculo em vez de compilá-lo primeiro?

Respostas:

Recursão da cauda faz faça sentido em (GHC) Haskell se o seu acumulador for rigoroso. Para demonstrar o problema, aqui está um "rastro" da sua definição recursiva de cauda de fac:

   fac 4
~> facRec 4 1
~> facRec 3 (1*4)
~> facRec 2 ((1*4)*3)
~> facRec 1 (((1*4)*3)*2)
~> facRec 0 ((((1*4)*3)*2)*1)
~> (((1*4)*3)*2) * 1
~> ((1*4)*3) * 2
~> (1*4) * 3
~> 1*4
~> 4 * 3
~> 12 * 2
~> 24 * 1
~> 24

O nível de indentação corresponde (aproximadamente) anível da pilha. Observe que o acumulador é avaliado apenas no final e isso pode causar um estouro de pilha. O truque, é claro, é tornar o acumulador rígido. É teoricamente possível mostrar que o facRec é estrito se for chamado em um contexto estrito, mas não conheço nenhum compilador que faça isso, o ATM. GHC faz otimização de chamada de cauda, ​​no entanto, para que o facRec chamadas usam espaço de pilha constante.

Pela mesma razão foldl" é geralmente preferido foldl, uma vez que o primeiro é estrito no acumulador.

Em relação à sua segunda parte, runhaskell/runghc é apenas um invólucro sobre o GHCi. Se o GHCi encontrar código compilado, ele usará isso; caso contrário, usará o interpretador de bytecode, que realiza poucas otimizações, portanto, não espere que ocorram otimizações sofisticadas.

No haskell, ajuda a escrever seu programa de maneira recursiva apenas se o seu acumulador for rigoroso e você precisar de um resultado completo.

Com o gHC "s runHaskell, o programa não seráotimizado, para que não haja uma análise de rigidez, portanto, você pode empilhar o estouro; enquanto, se você compilar com otimizações, o compilador poderá detectar que o acumulador precisa ser rigoroso e otimizar de acordo.

Para ver como as coisas acontecem de maneira diferente (ou não), a melhor maneira é inspecionar o idioma principal gerado, um bom post de Don Stewart explica as coisas . Muitos de seus posts no blog são interessantes se você estiver interessado em desempenho, a propósito.

Sua pergunta não está completa. Suponho que você queira dizer GHC e, pelo menos sem otimizações, a resposta é "sim" porque a função de trabalho (facRec no primeiro ou fac no segundo) tem uma aridade 2 em comparação com uma e a assembléia refletirá isso. Com otimizações ou com JHC, a resposta é provavelmente "não".