Ir al contenido principal

Actualización de «Normalización de expresiones aritméticas»

He actualizado las soluciones del ejercicio «Normalización de expresiones aritméticas» cuyo enunciado es

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

data Expr = V 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

esTermino :: Expr -> Bool
esNormal  :: Expr -> Bool
normal    :: Expr -> Expr

tales que

  • (esTermino a) se verifica si a es un término. Por ejemplo,
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,
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 ((a+b)·c = a·c+b·c y c·(a+b) = c·a+c·b). Por ejemplo,
λ> 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: Puedes consultar las soluciones aquí.