Première: je sais assez peu de choses sur Haskell, et mon temps total passé la programmation de la langue est pas plus de 8 heures réparties sur 5 ans ou bien, bien que j'ai lu beaucoup sur la langue. Ainsi, pardonnez sans aucun doute mon style horrible.
J'ai abordé ce problème car il me semblait être un moyen facile d'entrer dans un peu de programmation Haskell. Tout d'abord, je fait un type de données inspiré de l'échantillon:
data Expr = Const Int | Mult Expr Expr | Plus Expr Expr | Var String
Je l'ai fait un peu plus simple que l'original, et laissé de côté Minus, mais sinon il est le même.
J'ai rapidement découvert que les valeurs construites en utilisant par ex. "Const 4" n'étaient pas imprimables avec ce qui précède, car il n'y avait pas de fonction de show applicable. J'ai fait Expr une instance du Salon classe de type, et a fourni une définition simple de l'émission, en priorité des opérateurs en compte:
instance Show Expr where
show (Const n) = show n
show (Var n) = show n
show (Plus a b) = (show a) ++ "+" ++ (show b)
show (Mult a b) = "(" ++ (show a) ++ ") * (" ++ (show b) ++ ")"
Ensuite, ce fut la tâche de simplification lui-même. Comme le suggère Glomek, il y a un problème avec l'évaluation de tout ce qui consiste à utiliser une correspondance de modèle dans une seule fonction. Plus précisément, pour toute opération donnée (toutes les opérations de l'exemple sont binaires), vous souhaitez d'abord simplifier l'arborescence de gauche, puis l'arborescence de droite, puis simplifier l'Expr en cours en fonction de l'évaluation de ces sous-arborescences; par exemple. si les deux sont simplifiés en Const, vous pouvez remplacer l'ensemble de la sous-arborescence par l'opération évaluée. Cependant, la correspondance de modèle vous oblige à choisir quoi faire en fonction des enfants du nœud immédiat, plutôt que ce que les sous-arbres retournent après avoir été eux-mêmes simplifiés.
Ainsi, pour obtenir l'appariement de modèles afin de décider d'évaluer le nœud actuel ou non comme une sous-expression constante, il est important de simplifier les sous-arborescences, puis de les répartir en fonction de l'ensemble simplifié. Je l'ai fait en utilisant une fonction séparée appelée eval, dont le but est de faire correspondre les choses qui peuvent être réduites, en supposant que les sous-arbres ont déjà été réduits. Il gère également la multiplication par 0 et 1, et plus de 0:
-- Tries to evaluate any constant expressions.
eval :: Expr -> Expr
eval (Mult (Const a) (Const b)) = Const (a * b)
eval (Mult (Const a) b)
| a == 0 = Const 0
| a == 1 = b
| otherwise = (Mult (Const a) b)
eval (Mult a (Const b))
| b == 0 = Const 0
| b == 1 = a
| otherwise = (Mult a (Const b))
eval (Plus (Const a) (Const b)) = Const (a + b)
eval (Plus (Const a) b)
| a == 0 = b
| otherwise = (Plus (Const a) b)
eval (Plus a (Const b))
| b == 0 = a
| otherwise = (Plus a (Const b))
eval e = e
Maintenant que j'ai eval, et je sais qu'il est sûr d'appeler au niveau supérieur d'un arbre d'expression (à savoiril ne sera pas une récursion infinie), je peux l'appeler de Simplify après que j'ai simplifié les sous-arbres:
-- Tries to match evaluation rules after simplifying subtrees.
simplify :: Expr -> Expr
simplify (Plus a b) = eval (Plus (simplify a) (simplify b))
simplify (Mult a b) = eval (Mult (simplify a) (simplify b))
simplify e = e
Cette version de Simplify a de nombreuses limites: il ne distribuera pas une multiplication sur une sous-arborescence non Const , il ne réorganisera pas l'expression pour rapprocher les expressions constantes (donc l'équivalent de 1 + a + 2 ne sera pas simplifié en + 3), etc. Cependant, il fait les tâches de base.