Valores de polinomios y de expresiones

PorJosé A. Alonso 4-junio-201811-junio-2018

Las expresiones aritméticas construidas con una variables, los números enteros y las operaciones de sumar y multiplicar se pueden representar mediante el tipo de datos Exp definido por

   data Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp
              deriving Show

1 2	data Exp = Var \| Const Int \| Sum Exp Exp \| Mul Exp Exp deriving Show

Por ejemplo, la expresión 3+5x^2 se puede representar por

   exp1 :: Exp
   exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

1 2	exp1 :: Exp exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

Por su parte, los polinomios se pueden representar por la lista de sus
coeficientes. Por ejemplo, el polinomio 3+5x^2 se puede representar por [3,0,5].

Definir las funciones

   valorE :: Exp -> Int -> Int
   expresion :: [Int] -> Exp
   valorP :: [Int] -> Int -> Int

valorE :: Exp -> Int -> Int

expresion :: [Int] -> Exp

valorP :: [Int] -> Int -> Int

tales que

(valorE e n) es el valor de la expresión e cuando se sustituye su variable por n. Por ejemplo,

     λ> valorE (Sum (Const 3) (Mul Var (Mul Var (Const 5)))) 2
     23

1 2	λ> valorE (Sum (Const 3) (Mul Var (Mul Var (Const 5)))) 2 23

(expresion p) es una expresión aritmética equivalente al polinomio p. Por ejemplo,

     λ> expresion [3,0,5]
     Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5))))

1 2	λ> expresion [3,0,5] Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5))))

(valorP p n) es el valor del polinomio p cuando se sustituye su variable por n. Por ejemplo,

     λ> valorP [3,0,5] 2
     23

1 2	λ> valorP [3,0,5] 2 23

Comprobar con QuickCheck que, para todo polinomio p y todo entero n,

   valorP p n == valorE (expresion p) n

1	valorP p n == valorE (expresion p) n

Soluciones

import Test.QuickCheck

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp
           deriving Show
 
exp1 :: Exp
exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))
 
valorE :: Exp -> Int -> Int
valorE Var         n = n
valorE (Const a)   n = a
valorE (Sum e1 e2) n = valorE e1 n + valorE e2 n
valorE (Mul e1 e2) n = valorE e1 n * valorE e2 n
 
expresion :: [Int] -> Exp
expresion [a]   = Const a
expresion (a:p) = Sum (Const a) (Mul Var (expresion p))
 
valorP :: [Int] -> Int -> Int
valorP [a] _ = a
valorP (a:p) n = a + n * valorP p n
 
-- La propiedad es
prop_valor :: [Int] -> Int -> Property
prop_valor p n =
    not (null p) ==> 
    valorP p n == valorE (expresion p) n
 
-- La comprobación es
--    λ> quickCheck prop_valor
--    +++ OK, passed 100 tests.

import Test.QuickCheck

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp Exp

deriving Show

exp1 :: Exp

exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

valorE :: Exp -> Int -> Int

valorE Var n = n

valorE (Const a) n = a

valorE (Sum e1 e2) n = valorE e1 n + valorE e2 n

valorE (Mul e1 e2) n = valorE e1 n * valorE e2 n

expresion :: [Int] -> Exp

expresion [a] = Const a

expresion (a:p) = Sum (Const a) (Mul Var (expresion p))

valorP :: [Int] -> Int -> Int

valorP [a] _ = a

valorP (a:p) n = a + n * valorP p n

-- La propiedad es

prop_valor :: [Int] -> Int -> Property

prop_valor p n =

not (null p) ==>

valorP p n == valorE (expresion p) n

-- La comprobación es

-- λ> quickCheck prop_valor

-- +++ OK, passed 100 tests.

3 Comentarios

import Test.QuickCheck

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp Exp
         deriving Show

exp1 :: Exp
exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

valorE :: Exp -> Int -> Int
valorE exp x = opera exp
  where opera (Const c)       = c
        opera (Sum Var Var)   = x + x
        opera (Sum Var exp2)  = x + opera exp2
        opera (Sum exp1 Var)  = opera exp1 + x
        opera (Sum exp1 exp2) = opera exp1 + opera exp2
        opera (Mul Var Var)   = x * x
        opera (Mul Var exp2)  = x * opera exp2
        opera (Mul exp1 Var)  = opera exp1 * x
        opera (Mul exp1 exp2) = opera exp1 * opera exp2

expresion :: [Int] -> Exp
expresion []     = Const 0
expresion [e]    = Const e
expresion (x:xs) = Sum (Const x) (Mul Var (expresion xs))

valorP :: [Int] -> Int -> Int
valorP xs x = construye xs 1
 where construye (y:ys) v = v*y + construye ys (v*x)
       construye _ _      = 0

prop_valor :: [Int] -> Int -> Bool
prop_valor p n = valorP p n == valorE (expresion p) n

import Test.QuickCheck

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp Exp

deriving Show

exp1 :: Exp

exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

valorE :: Exp -> Int -> Int

valorE exp x = opera exp

where opera (Const c) = c

opera (Sum Var Var) = x + x

opera (Sum Var exp2) = x + opera exp2

opera (Sum exp1 Var) = opera exp1 + x

opera (Sum exp1 exp2) = opera exp1 + opera exp2

opera (Mul Var Var) = x * x

opera (Mul Var exp2) = x * opera exp2

opera (Mul exp1 Var) = opera exp1 * x

opera (Mul exp1 exp2) = opera exp1 * opera exp2

expresion :: [Int] -> Exp

expresion [] = Const 0

expresion [e] = Const e

expresion (x:xs) = Sum (Const x) (Mul Var (expresion xs))

valorP :: [Int] -> Int -> Int

valorP xs x = construye xs 1

where construye (y:ys) v = v*y + construye ys (v*x)

construye _ _ = 0

prop_valor :: [Int] -> Int -> Bool

prop_valor p n = valorP p n == valorE (expresion p) n

Responder

valorE Var n = n
valorE (Const a) _ = a
valorE (Sum a b) n = (valorE a n) + (valorE b n)
valorE (Mul a b) n = (valorE a n) * (valorE b n)

expresion [x] = Const x
expresion (x:xs) =
   Sum (Const x) (Mul Var (expresion xs))

valorP = valorE . expresion

valorE Var n = n

valorE (Const a) _ = a

valorE (Sum a b) n = (valorE a n) + (valorE b n)

valorE (Mul a b) n = (valorE a n) * (valorE b n)

expresion [x] = Const x

expresion (x:xs) =

Sum (Const x) (Mul Var (expresion xs))

valorP = valorE . expresion

Responder

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp
           deriving Show

valorE :: Exp -> Int -> Int
valorE Var n = n
valorE (Const c) n = c
valorE (Sum e1 e2) n = (valorE e1 n) + (valorE e2 n)
valorE (Mul e1 e2) n = (valorE e1 n) * (valorE e2 n)


expresion :: [Int] -> Exp
expresion []     = Const 0
expresion [c]    = Const c
expresion (x:xs) = Sum (Const x) (Mul Var (expresion xs))

valorP :: [Int] -> Int -> Int
valorP xs n = foldr f 0 xs
  where f x y = x + y*n

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp Exp

deriving Show

valorE :: Exp -> Int -> Int

valorE Var n = n

valorE (Const c) n = c

valorE (Sum e1 e2) n = (valorE e1 n) + (valorE e2 n)

valorE (Mul e1 e2) n = (valorE e1 n) * (valorE e2 n)

expresion :: [Int] -> Exp

expresion [] = Const 0

expresion [c] = Const c

expresion (x:xs) = Sum (Const x) (Mul Var (expresion xs))

valorP :: [Int] -> Int -> Int

valorP xs n = foldr f 0 xs

where f x y = x + y*n

Responder

Valores de polinomios y de expresiones

Soluciones

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico