Recursion de queue dans Haskell

Question

J'essaie de comprendre la récurrence de la queue chez Haskell. Je pense que je comprends ce que c'est et comment cela fonctionne mais je voudrais m'assurer que je ne fais pas de bêtises.

Voici la définition factoriel "standard":

factorial 1 = 1 
factorial k = k * factorial (k-1) 

Lors de l'exécution, par exemple, factorial 3, ma fonction sera lui-même appeler 3 fois (donner ou prendre). Cela pourrait poser un problème si je voulais calculer factorielle 99999999 car je pourrais avoir un débordement de pile. Après que j'arrive à factorial 1 = 1 je devrai "revenir" dans la pile et multiplier toutes les valeurs, donc j'ai 6 opérations (3 pour appeler la fonction elle-même et 3 pour multiplier les valeurs).

Maintenant, je vous présente une autre possible mise en œuvre factoriel:

factorial 1 c = c 
factorial k c = factorial (k-1) (c*k) 

Celui-ci est récursive aussi. Il s'appellera 3 fois. Mais il n'a pas alors le problème de devoir "revenir" pour calculer les multiplications de tous les résultats, car je passe déjà le résultat en argument de la fonction.

Ceci est, pour ce que j'ai compris, ce que Tail Recursion est à propos. Maintenant, il semble un peu mieux que le premier, mais vous pouvez toujours avoir des débordements de pile aussi facilement. J'ai entendu dire que le compilateur de Haskell va convertir les fonctions Tail-Recursive en boucles en arrière-plan. Je suppose que c'est la raison pour laquelle il est payant de faire des fonctions récursives de la queue?

Si c'est la raison alors il n'y a absolument aucun besoin d'essayer de rendre les fonctions récursives si le compilateur ne va pas faire ce tour intelligent - ai-je raison? Par exemple, bien qu'en théorie le compilateur C# puisse détecter et convertir les fonctions récursives de la queue en boucles, je sais (du moins c'est ce que j'ai entendu) qu'à l'heure actuelle il ne le fait pas. Il n'y a donc absolument aucun intérêt à rendre les fonctions récursives de nos jours. Est-ce que c'est ça?

Merci!

Answer 1

Il y a deux problèmes ici. L'un est la récurrence de la queue en général, et l'autre est la façon dont Haskell gère les choses.

En ce qui concerne la récursivité de la queue, vous semblez avoir la définition correcte. La partie utile est, parce que seul le résultat final de chaque appel récursif est nécessaire, les appels antérieurs n'ont pas besoin d'être conservés sur la pile. Au lieu de "s'appeler", la fonction fait quelque chose de plus proche du "remplacement" lui-même, qui finit par ressembler à une boucle itérative. C'est une optimisation assez simple que les compilateurs décents fourniront généralement. Le deuxième numéro est évaluation paresseuse. Étant donné que Haskell n'évalue l'expression que selon les besoins, la récursion par défaut ne fonctionne pas de la manière habituelle. Au lieu de remplacer chaque appel au fur et à mesure, il construit une énorme pile imbriquée de "thunks", c'est-à-dire des expressions dont la valeur n'a pas encore été demandée. Si cette pile de thunk devient assez grande, elle produira en effet un débordement de pile.

Il y a en fait deux solutions en Haskell, en fonction de ce que vous devez faire:

• Si le résultat est constitué des constructeurs de données imbriquées - comme la production d'une liste - alors vous voulez éviter récursion de la queue; placez plutôt la récursion dans l'un des champs du constructeur. Cela permettra au résultat d'être paresseux et ne provoquera pas de débordements de pile.Si le résultat consiste en une seule valeur, vous voulez l'évaluer strictement, de sorte que chaque étape de la récursivité soit forcée dès que la valeur finale est requise. Cela donne la pseudo-itération habituelle que vous attendez d'une récursion de queue.

De plus, gardez à l'esprit que GHC est sacrément intelligent et, si vous compilez avec des optimisations, il sera souvent repérer les endroits où l'évaluation doit être stricte et prendre soin d'elle pour vous. Cela ne fonctionnera pas dans GHCi, cependant.

Answer 2

Vous devez utiliser les mécanismes intégrés, alors vous ne devez pas penser à des façons de rendre votre récursive fonction

fac 0 = 1 
fac n = product [1..n] 

ou si le produit n'a pas été déjà défini:

fac n = foldl' (*) 1 [1..n] 

(voir http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 dont pli ... version à utiliser)