10-diciembre-2014 – Exercitium

Normalización de expresiones aritméticas

PorJosé A. Alonso 10-diciembre-201425-abril-2021

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)

Día: 10-diciembre-2014

Normalización de expresiones aritméticas

Enunciado

Soluciones

Entradas recientes

Buscar

Correo electrónico