Normalización de expresiones aritméticas
El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos
1 2 3 4 |
data Expr = Var String | S Expr Expr | P Expr Expre deriving (Eq, Show) |
Por ejemplo, x*(y+z)
se representa por (P (V "x") (S (V "y") (V "z")))
Una expresión es un término si es un producto de variables. Por ejemplo, x*(y*z)
es un término pero x+(y*z)
ni x*(y+z)
lo son.
Una expresión está en forma normal si es una suma de términos. Por ejemplo, x*(y*z)
y x+(y*z)
están en forma normal; pero x*(y+z)
y (x+y)*(x+z)
no lo están.
Definir la función
1 2 3 |
esTermino :: Expr -> Bool esTermino :: Expr -> Bool normal :: Expr -> Expr |
tales que
- (esTermino a) se verifica si a es un término. Por ejemplo,
1 2 3 4 |
esTermino (V "x") == True esTermino (P (V "x") (P (V "y") (V "z"))) == True esTermino (P (V "x") (S (V "y") (V "z"))) == False esTermino (S (V "x") (P (V "y") (V "z"))) == False |
- (esNormal a) se verifica si a está en forma normal. Por ejemplo,
1 2 3 4 5 6 |
esNormal (V "x") == True esNormal (P (V "x") (P (V "y") (V "z"))) == True esNormal (S (V "x") (P (V "y") (V "z"))) == True esNormal (P (V "x") (S (V "y") (V "z"))) == False esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False esNormal (S (P (V "x") (V "y")) (S (V "z") (V "x"))) == True |
- (normal e) es la forma normal de la expresión e obtenida aplicando, mientras que sea posible, las propiedades distributivas:
1 2 |
(a+b)*c = a*c+b*c c*(a+b) = c*a+c*b |
Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 |
λ> normal (P (S (V "x") (V "y")) (V "z")) S (P (V "x") (V "z")) (P (V "y") (V "z")) λ> normal (P (V "z") (S (V "x") (V "y"))) S (P (V "z") (V "x")) (P (V "z") (V "y")) λ> normal (P (S (V "x") (V "y")) (S (V "u") (V "v"))) S (S (P (V "x") (V "u")) (P (V "x") (V "v"))) (S (P (V "y") (V "u")) (P (V "y") (V "v"))) λ> normal (S (P (V "x") (V "y")) (V "z")) S (P (V "x") (V "y")) (V "z") λ> normal (V "x") V "x" |
Comprobar con QuickCheck que para cualquier expresión e, (normal e) está en forma normal y que (normal (normal e)) es igual a (normal e).
Nota. Para la comprobación se usará el siguiente generador de expresiones aritméticas
1 2 3 4 5 6 7 8 9 10 11 |
import Test.QuickCheck import Control.Monad instance Arbitrary Expr where arbitrary = sized arb where arb 0 = liftM V arbitrary arb n | n > 0 = oneof [liftM V arbitrary, liftM2 S sub sub, liftM2 P sub sub] where sub = arb (n `div` 2) |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import Test.QuickCheck import Control.Monad data Expr = V String | S Expr Expr | P Expr Expr deriving (Eq, Show) esTermino :: Expr -> Bool esTermino (V _) = True esTermino (S _ _) = False esTermino (P a b) = esTermino a && esTermino b esNormal :: Expr -> Bool esNormal (S a b) = esNormal a && esNormal b esNormal a = esTermino a normal :: Expr -> Expr normal (V v) = V v normal (S a b) = S (normal a) (normal b) normal (P a b) = p (normal a) (normal b) where p (S a b) c = S (p a c) (p b c) p a (S b c) = S (p a b) (p a c) p a b = P a b prop_normal :: Expr -> Bool prop_normal e = esNormal (normal e) && normal (normal e) == normal e -- La comprobación es -- λ> quickCheck prop_normal -- +++ OK, passed 100 tests. instance Arbitrary Expr where arbitrary = sized arb where arb 0 = liftM V arbitrary arb n | n > 0 = oneof [liftM V arbitrary, liftM2 S sub sub, liftM2 P sub sub] where sub = arb (n `div` 2) |
2 Comentarios