Menu Close

Operaciones con polinomios como diccionarios

Los polinomios se pueden representar mediante diccionarios con los exponentes como claves y los coeficientes como valores.

El tipo de los polinomios con coeficientes de tipo a se define por

   type Polinomio a = M.Map Int a

Dos ejemplos de polinomios (que usaremos en los ejemplos) son

   3 + 7x - 5x^3
   4 + 5x^3 + x^5

se definen por

  ejPol1, ejPol2 :: Polinomio Int
  ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
  ejPol2 = M.fromList [(0,4),(3,5),(5,1)]

Definir las funciones

   sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
   multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
   multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a

tales que

  • (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,
     ghci> sumaPol ejPol1 ejPol2
     fromList [(0,7),(1,7),(5,1)]
     ghci> sumaPol ejPol1 ejPol1
     fromList [(0,6),(1,14),(3,-10)]
  • (multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo,
     ghci> multPorTerm (2,3) (M.fromList [(0,4),(2,1)])
     fromList [(2,12),(4,3)]
  • (multPol p q) es el producto de los polinomios p y q. Por ejemplo,
     ghci> multPol ejPol1 ejPol2
     fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
     ghci> multPol ejPol1 ejPol1
     fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
     ghci> multPol ejPol2 ejPol2
     fromList [(0,16),(3,40),(5,8),(6,25),(8,10),(10,1)]

Soluciones

import qualified Data.Map as M
 
type Polinomio a = M.Map Int a 
 
ejPol1, ejPol2 :: Polinomio Int
ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
ejPol2 = M.fromList [(0,4),(3,5),(5,1)]
 
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q = 
    M.filter (/=0) (M.unionWith (+) p q)
 
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPorTerm (n,a) p =
    M.map (*a) (M.mapKeys (+n) p)
 
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q
    | M.null p  = M.empty
    | otherwise = sumaPol (multPorTerm t q) (multPol r q)
    where (t,r) = M.deleteFindMin p

5 soluciones de “Operaciones con polinomios como diccionarios

  1. albcercid
     
    type Polinomio a = M.Map Int a
     
     
    ejPol1, ejPol2 :: Polinomio Int
    ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
    ejPol2 = M.fromList [(0,4),(3,5),(5,1)]
     
    sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
    sumaPol m1 = (M.filter (/= 0)).(M.unionWith (+) m1)
     
    multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm (a,b) = (M.mapKeys (+a)).(M.map (*b))
     
    multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
    multPol m1 m2 = aux (M.assocs m1)
       where aux [] = M.fromList [(0,0)]
             aux ((a,b):xs) = sumaPol (multPorTerm (a,b) m2) (aux xs)
  2. joscasgom1
     
    import Data.Map as M
     
    type Polinomio a = M.Map Int a
     
    sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
    sumaPol d1 d2 =M.filter (/=0)( M.unionWith (+) d1 d2)
     
    multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm (a,b) d =M.mapKeys (+a) (M.map (*b) d)
     
    multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
    multPol p q = sumasPol (prod p q)
     
    prod :: (Eq a,Num a) => Polinomio a -> Polinomio a -> [Polinomio a]
    prod p q | M.null p = []
               | otherwise = multPorTerm (M.findMin p) q : prod (M.deleteMin p) q
     
    sumasPol :: (Eq a, Num a) => [Polinomio a] -> Polinomio a
    sumasPol [] = M.empty
    sumasPol (x:xs) = sumaPol x (sumasPol xs)
  3. paumacpar
    sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
    sumaPol p q = M.filter (/=0) (M.unionWith (+) p q)
     
    multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm (n,a) p = M.mapKeys (+n) (M.mapWithKey f p)
      where f _ x = a*x
     
    multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
    multPol p q |  M.null p || M.null q = M.empty
                | otherwise = sumaPol (multPorTerm (n,a) q) (multPol r q)
      where ((n,a),r) = M.deleteFindMax p
  4. enrnarbej
    import Data.Map
    import Prelude hiding (map,filter)
     
    type Polinomio a = Map Int a
     
    sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
    sumaPol p = filter (/=0) . unionWith (+) p
     
    multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm (n,a)= map (*a) . mapKeys (+n) 
     
    multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
    multPol p q = foldlWithKey' f empty q
                where
                 f s k v = (sumaPol s . multPorTerm (k,v)) p
  5. Juanjo Ortega (juaorture)
    import Data.Map as M
     
    sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
    sumaPol p q | M.null p = q
                | M.null q = p
                | otherwise = limpia 0 (aux (max (fst (findMax p)) (fst (findMax q))))
            where aux n | n < 0      = p
                        | member n q = insertWithKey (a b c -> c + b) n (q!n) (aux (n-1))  
                        | otherwise  = aux (n-1)
     
    multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm (k,x) p = aux 0
                where aux n | n > fst (findMax p) = empty
                            | member n p      = insert (k+n) (x*(p!n)) (aux (n+1))
                            | otherwise       = aux (n+1)
     
    -- Otra definición usando map
    multPorTerm' :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm' (k,x) p = M.map (*x) (mapKeys (+k) p)
     
    multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
    multPol p q = sumaPolList [multPorTerm' (k,x) p | k <- keys q, let x = q ! k]
              where sumaPolList []     = empty
                    sumaPolList (x:xs) = sumaPol x (sumaPolList xs)
     
     
    limpia :: (Eq a, Num a) => Int -> Polinomio a -> Polinomio a
    limpia n s | n > fst (findMax s) = s
               | not (member n s)    = limpia (n+1) s
               | s ! n == 0          = delete n (limpia (n+1) s)
               | otherwise           = limpia (n+1) s

Escribe tu solución

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