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 de l'optimisation!
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 des 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 qu' (*) 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 qu'on appelle gardé la récursivité (bien qu'il est généralement mentionné comme tel avec les 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).
Maintenant, regardons 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
Donc 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 faut-il plus d'étapes que l' facSlow 5, il crée également un imbriquée thunk (ici, en tant que {...}) - le besoin d'un espace supplémentaire pour elle - qui décrit l'avenir de calcul, la imbriquée de multiplications à effectuer.
Cette 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 $! à 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)
Cela oblige facS' , pour ê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 de l' facS' à s'appliquer.)
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
- La 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 à propos de
foldr et foldl par exemple, et de les tester les uns contre les autres.
Essayez 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 qu' 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 devrez peut-être ajuster le nombre de zéros en fonction de ce matériel que vous utilisez.
