Menu Close

Valores de polinomios y de expresiones

José A. Alonso,

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. Responder
    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. Responder
    Á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. Responder
    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.