Ne Haskell ont récursives terminales de l'optimisation?

Haskell utilise paresseux-évaluation à mettre en œuvre la récursivité, donc, traite de quelque chose comme une promesse de fournir une valeur en cas de besoin (ce qui est appelé un thunk). Thunks se réduit uniquement la quantité nécessaire de procéder, sans plus. Cela ressemble à la façon de simplifier une expression mathématique, de sorte qu'il est utile de penser à elle de cette façon. Le fait que l'ordre d'évaluation est pas spécifié par votre code permet au compilateur de faire beaucoup de même plus sage d'optimisations que juste la queue-appel d'élimination que vous êtes habitué. Compiler avec -O2 si vous voulez optimisation de la!

Nous allons voir comment nous évaluons facSlow 5 comme une étude de cas:

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

Ainsi, tout comme vous inquiet, nous avons une accumulation de chiffres avant les calculs se produire, mais contrairement à vous inquiète, il n'y a pas de pile de facSlow appels de fonction suspendu autour de l'attente à la fin de chaque réduction est appliqué et s'en va, laissant un frame de pile dans son sillage (c'est parce que (*) est stricte et donc déclenche l'évaluation de son deuxième argument).

Haskell fonctions récursives ne sont pas évalués dans un très récursive façon! La seule pile des appels de traîner sont les multiplications eux-mêmes. Si (*) est considérée comme une stricte des données constructeur, c'est ce qui est connu comme gardé la récursivité (bien qu'il est généralement mentionné comme tel avec non-strict des données constructeurs, où ce qui est laissé dans son sillage sont les constructeurs de données - lorsque, forcé par accès).

Examinons maintenant la queue-récursive 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

De sorte que vous pouvez voir comment la queue de la récursivité par lui-même n'a pas sauvé, vous avez tout le temps ou l'espace. Non seulement il prendre des mesures plus globales que facSlow 5, il crée également un imbriquée thunk (montré ici comme {...}) - besoin d'un espace supplémentaire pour elle - qui décrit l'avenir de calcul, la imbriquée de multiplications à effectuer.

Ce thunk est ensuite décortiquée en parcourant il vers le bas, en recréant le calcul sur la pile. Il y a aussi un risque de causer un débordement de pile avec de très longs calculs, pour les deux versions.

Si nous voulons la main-d'optimiser cela, tout ce que nous devons faire c'est de stricte. Vous pouvez utiliser l'application stricte de l'opérateur $! de définir

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

Cette forces facS' être rigoureux dans son deuxième argument. (C'est déjà le strict dans son premier argument parce que cela a à être évalués afin de décider quelle est la définition du facS' applique.)

Parfois la rigueur peut aider énormément, parfois, c'est une grosse erreur parce que la paresse est plus efficace. Ici c'est une bonne idée:

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

Qui est ce que tu voulais faire, je pense.

Résumé

• Si vous souhaitez optimiser votre code, la première étape consiste à compiler avec -O2
• Queue de la récursivité n'est bon que quand il n'y a pas de thunk build-up, et l'ajout de rigueur permet généralement d'éviter, si et, le cas échéant. Ce qui se passe quand vous êtes en train de construire un résultat qui est nécessaire plus tard, tout à la fois.
• Parfois la queue de la récursivité est un mauvais plan et gardé la récursivité est un meilleur ajustement, c'est à dire lorsque le résultat que vous êtes en train de construire sera nécessaire, bit par bit, en portions. Voir cette question sur foldr et foldl par exemple, et de les tester les uns contre les autres.

Essayer ces deux:

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 est la queue récursive, alors que foldr1 effectue gardé la récursivité de sorte que le premier élément est immédiatement présenté pour la poursuite du traitement/de l'accès. _{(Le premier "parenthesizes" de la gauche à la fois, (...((s+s)+s)+...)+s, forçant sa liste d'entrée pleinement à sa fin et la construction d'un grand sens de l'avenir de calcul beaucoup plus tôt que ses résultats complets sont nécessaires; la deuxième parenthesizes pour le droit progressivement, s+(s+(...+(s+s)...)), la consommation de la liste d'entrée peu à peu, donc, le tout est de pouvoir fonctionner dans de la constante de l'espace, avec les optimisations).}

Vous pourriez avoir besoin d'ajuster le nombre de zéros en fonction de ce matériel que vous utilisez.

Vous devriez consulter l'article de wiki sur la queue de la récursivité en Haskell. En particulier, en raison de l'évaluation de l'expression, le genre de la récursivité vous voulez, c'est gardé la récursivité. Si vous travailler sur les détails de ce qui se passe sous le capot (dans la machine abstraite pour Haskell), vous obtenez le même genre de chose qu'avec de la queue de la récursivité dans le strict langues. Parallèlement à cela, vous avez une syntaxe uniforme pour les paresseux fonctions (queue de récursivité permettra de vous lier à une évaluation rigoureuse, alors que gardé la récursivité fonctionne plus naturellement).

(Et dans l'apprentissage de Haskell, le reste des pages du wiki sont génial, trop!)