Menu Close

Normalización de expresiones aritméticas

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

   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

   esTermino :: Expr -> Bool
   esTermino :: 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
     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. Para la comprobación se usará el siguiente generador de expresiones aritméticas

   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

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)
Avanzado

2 soluciones de “Normalización de expresiones aritméticas

  1. albcercid
    esTermino :: Expr -> Bool
    esTermino (V _) = True
    esTermino (P a b) = esTermino a && esTermino b
    esTermino (S _ _) = False
     
    esNormal :: Expr -> Bool
    esNormal (V _) = True
    esNormal (S a b) = esNormal a && esNormal b
    esNormal (P (S _ _) _) = False
    esNormal (P _ (S _ _)) = False
    esNormal (P a b) = esNormal a && esNormal b
     
     
    normal (V a) = V a
    normal (S a b) = S (normal a) (normal b)
    normal (P (S a b) (S c d)) = S (S (normal (P a c)) (normal (P a d)))
                                  (S (normal (P b c)) (normal (P b d)))
    normal (P (S a b) c) = S (normal (P a c)) (normal (P b c))
    normal (P a (S b c)) = S (normal (P a b)) (normal (P a c))
    normal (P a b) | esNormal (P a b) = P a b
                   | otherwise = normal (P (normal a) (normal b))
     
     
    prop_normal :: Expr -> Bool
    prop_normal e = esNormal t && normal t == t
        where t = normal e
  2. enrnarbej
    import Test.QuickCheck
    import Control.Monad
     
    esTermino :: Expr -> Bool
    esTermino (V   a     ) = True
    esTermino (S xs ys   ) = False
    esTermino (P xs ys   ) = esTermino xs && esTermino ys
     
    esNormal  :: Expr -> Bool
    esNormal (V a)   = True
    esNormal (S xs ys) = esNormal xs && esNormal ys
    esNormal (P xs ys) = esTermino xs && esTermino ys
     
     
    normal    :: Expr -> Expr
    normal = until esNormal normalAux
     
    normalAux    :: Expr -> Expr
    normalAux  (V  a)    = V a
    normalAux  (S xs ys)  = S (normal xs) (normal ys)
    normalAux  (P xs (S as bs)) = S (normal (P xs as)) (normal (P  xs bs))
    normalAux  (P (S as bs) xs) = S (normal (P as xs)) (normal (P  bs xs))
    normalAux  (P x y)          = P (normal x) (normal y)
     
    prop_normal1 :: Expr -> Bool
    prop_normal1 = esNormal . normal
     
    prop_normal2 :: Expr -> Bool
    prop_normal2 e = normal (normal e) == normal e

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.