Tenho tentado explorar as possibilidades de recursão em Haskell, mas não sei muito sobre como melhorar a eficiência ao enfrentar grandes recursões. Hoje, eu queria fazer uma função que calculasse números de Stirling de segundo tipo:
factorial :: Integer -> Integer
factorial n = helper n 1
where
helper 1 a = a
helper n a = helper (n-1) (a*n)
stirling :: Integer -> Integer -> Integer
stirling n 1 = 1
stirling n 2 = ((2 ^n)- 2) `div` 2
stirling n k
| k > n = 0
| k == n = 1
| k == (n-1) = (factorial n) `div` (factorial 2 * (factorial(n-2)))
| otherwise = stirling (n-1) (k-1) + k *(stirling (n-1) k)
Tenho tentado criar uma função auxiliar, assim como na definição fatorial, que pudesse evitar a inconveniência da avaliação preguiçosa de Haskell consumir muitos recursos de memória. Quero fazer o mesmo, calculando o produto em cada chamada do
k *(stirling (n-1) k)
recursão, mas não peguei o jeito. Alguma ideia?
PD: O código já funciona bem, mas sou novo em Haskell e ainda não sei quais são as possibilidades. Qualquer melhoria é bem-vinda (embora eu não use nenhuma biblioteca; quero aprender o básico antes de entrar nisso).