Enunciado
-- 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) |
-- 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
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) |
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)
Se puede imprimir o compartir con
Funciona, pero no parece ser muy eficiente.