Normalización de expresiones aritméticas
Enunciado
|
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 43 44 45 46 47 48 |
-- El siguiente tipo de dato representa expresiones construidas con -- variables, sumas y productos -- data Expr = V String -- | S Expr Expr -- | P Expr Expr -- 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á en forma normal; pero x*(y+z) y -- (x+y)*(x+z) no lo están. -- -- Definir la función -- normal :: Expr -> Expr -- tal que (normal e) es la forma normal de la expresión e obtenida -- aplicando, mientras que sea posible, las propiedades distributivas: -- (a+b)*c = a*c+b*c -- c*(a+b) = c*a+c*b -- Por ejemplo, -- ghci> normal (P (S (V "x") (V "y")) (V "z")) -- S (P (V "x") (V "z")) (P (V "y") (V "z")) -- ghci> normal (P (V "z") (S (V "x") (V "y"))) -- S (P (V "z") (V "x")) (P (V "z") (V "y")) -- ghci> 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"))) -- ghci> normal (S (P (V "x") (V "y")) (V "z")) -- S (P (V "x") (V "y")) (V "z") -- ghci> normal (V "x") -- V "x" -- -- Comprobar con QuickCheck (usando la función esNormal del ejercicio -- del 2 de diciembre) 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: -- 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 |
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 -- ghci> 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) |