Menu Close

Valores de polinomios y de expresiones

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

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

   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

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
  • (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))))
  • (valorP p n) es el valor del polinomio p cuando se sustituye su variable por n. Por ejemplo,
     λ> 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

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.
Medio

3 soluciones de “Valores de polinomios y de expresiones

  1. jaibengue
    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
  2. Álvaro Gutiérrez
    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
  3. Maria Ruiz
     
    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

Escribe tu solución

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