Haskell tem otimização recursiva de cauda?

Eu descobri o comando "time" no Unix hoje e pensei em usá-lo para verificar a diferença nos tempos de execução entre funções recursivas de cauda e recursivas normais em Haskell.

Eu escrevi as seguintes funções:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

Eles são válidos tendo em mente que eram apenas para uso com este projeto, então não me preocupei em verificar se há zeros ou números negativos.

No entanto, ao escrever um método principal para cada um, compilá-los e executá-los com o comando "time", ambos tinham tempos de execução semelhantes com a função recursiva normal ultrapassando a recursiva final. Isso é contrário ao que eu ouvi em relação à otimização recursiva de cauda no lisp. Qual é o motivo disso?

Haskell usa avaliação preguiçosa para implementar recursão, então trata qualquer coisa como uma promessa de fornecer um valor quando necessário (isso é chamado de conversão). Thunks são reduzidos apenas o necessário para prosseguir, nada mais. Isso se assemelha à maneira como você simplifica uma expressão matematicamente, portanto, é útil pensar dessa maneira. O fato de que a ordem de avaliação não é especificada por seu código permite que o compilador faça muitas otimizações ainda mais inteligentes do que apenas a eliminação de chamada final a que você está acostumado. Compile com -O2se quiser otimização!

Vamos ver como avaliamos facSlow 5como um estudo de caso:

facSlow 5
5 * facSlow 4            -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3)       -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2))  -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

Assim como você se preocupa, temos um acúmulo de números antes que qualquer cálculo aconteça, mas ao contrário de você se preocupa, não há uma pilha de facSlowchamadas de função esperando para terminar - cada redução é aplicada e vai embora, deixando um quadro de pilha em seu wake (isso porque (*)é estrito e, portanto, aciona a avaliação de seu segundo argumento).

As funções recursivas de Haskell não são avaliadas de uma forma muito recursiva! A única pilha de chamadas suspensas são as próprias multiplicações. Se (*)for visto como um construtor de dados estrito, isso é conhecido como recursão protegida (embora seja geralmente referida como tal com não construtores de dados estritos, onde o que resta em seu rastro são os construtores de dados - quando forçado por acesso posterior).

Agora vamos dar uma olhada na cauda recursiva fac 5:

fac 5
fac' 5 1
fac' 4 {5*1}       -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}}    -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}        -- the thunk "{...}" 
(2*{3*{4*{5*1}}})        -- is retraced 
(2*(3*{4*{5*1}}))        -- to create
(2*(3*(4*{5*1})))        -- the computation
(2*(3*(4*(5*1))))        -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120

Então você pode ver como a recursão da cauda por si só não economizou tempo ou espaço. Ele não apenas leva mais etapas gerais do que facSlow 5, mas também cria uma conversão aninhada (mostrada aqui como {...}) - precisando de um espaço extra para ele - que descreve a computação futura, as multiplicações aninhadas a serem realizadas.

Essa conversão é então desvendada ao atravessá- la até o final, recriando a computação na pilha. Também existe o perigo de causar estouro de pilha com cálculos muito longos, para ambas as versões.

Se quisermos otimizar isso manualmente, tudo o que precisamos fazer é torná-lo rígido. Você pode usar o operador de aplicativo estrito $!para definir

facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
    facS' 1 y = y
    facS' x y = facS' (x-1) $! (x*y) 

Isso obriga facS'a ser estrito em seu segundo argumento. (Já é estrito em seu primeiro argumento porque tem que ser avaliado para decidir qual definição facS'aplicar.)

Às vezes, a rigidez pode ajudar enormemente, às vezes é um grande erro porque a preguiça é mais eficiente. Aqui é uma boa ideia:

facSlim 5
facS' 5 1
facS' 4 5 
facS' 3 20
facS' 2 60
facS' 1 120
120

Que é o que você queria alcançar, eu acho.

Resumo

• Se você deseja otimizar seu código, a primeira etapa é compilar com -O2
• A recursão de cauda só é boa quando não há acúmulo de conversão, e adicionar rigidez geralmente ajuda a evitá-la, se e quando apropriado. Isso acontece quando você está construindo um resultado que será necessário posteriormente de uma só vez.
• Às vezes, a recursão da cauda é um plano ruim e a recursão protegida é um ajuste melhor, ou seja, quando o resultado que você está construindo será necessário aos poucos, em porções. Veja esta pergunta sobre foldre, foldlpor exemplo, e teste-os uns contra os outros.

Experimente estes dois:

length $ foldl1 (++) $ replicate 1000 
    "The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000 
    "The number of reductions performed is more important than tail recursion!!!"

foldl1é recursivo na cauda, ​​enquanto foldr1executa recursão protegida de modo que o primeiro item seja imediatamente apresentado para processamento / acesso posterior. _{(O primeiro "coloca entre parênteses" à esquerda de uma vez, (...((s+s)+s)+...)+sforçando sua lista de entrada totalmente ao seu fim e construindo uma grande quantidade de computação futura muito mais cedo do que seus resultados completos são necessários; o segundo parênteses à direita gradualmente s+(s+(...+(s+s)...)), consumindo a entrada listar pouco a pouco, para que tudo funcione em espaço constante, com otimizações).}

Pode ser necessário ajustar o número de zeros dependendo de qual hardware você está usando.

Deve ser mencionado que a facfunção não é uma boa candidata para recursão protegida. A recursão da cauda é o caminho a percorrer aqui. Devido à preguiça, você não está obtendo o efeito do TCO em sua fac'função porque os argumentos do acumulador continuam construindo grandes thunks, que quando avaliados exigirão uma pilha enorme. Para evitar isso e obter o efeito desejado do TCO, você precisa tornar esses argumentos do acumulador estritos.

{-# LANGUAGE BangPatterns #-}

fac :: (Integral a) => a -> a
fac x = fac' x 1 where
  fac' 1  y = y
  fac' x !y = fac' (x-1) (x*y)

Se você compilar usando -O2(ou apenas -O) GHC, provavelmente fará isso sozinho na fase de análise de rigidez .

Você deve verificar o artigo wiki sobre recursão da cauda em Haskell . Em particular, por causa da avaliação da expressão, o tipo de recursão que você deseja é a recursão protegida . Se você descobrir os detalhes do que está acontecendo por baixo do capô (na máquina abstrata de Haskell), obterá o mesmo tipo de coisa que a recursão de cauda em linguagens estritas. Junto com isso, você tem uma sintaxe uniforme para funções preguiçosas (a recursão final vai amarrá-lo a uma avaliação estrita, enquanto a recursão protegida funciona mais naturalmente).

(E ao aprender Haskell, o resto das páginas wiki são fantásticas também!)

Se bem me lembro, o GHC otimiza automaticamente funções recursivas simples em funções otimizadas recursivas de cauda.