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,
     λ> sumaPol ejPol1 ejPol2
     fromList [(0,7),(1,7),(5,1)]
     λ> 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,
     λ> 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,
     λ> multPol ejPol1 ejPol2
     fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
     λ> multPol ejPol1 ejPol1
     fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
     λ> 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

3 soluciones de “Operaciones con polinomios como diccionarios

  1. melgonaco
    import 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) (unionWith (+) p q)
     
    multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm (n,a) p = mapKeys (+n) (fmap (*a) p)
     
    multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
    multPol p q = foldl1 (sumaPol) xs
      where xs = [multPorTerm (n,a) q | (n,a) <- toList p]
  2. Enrique Zubiría
    import 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 polA polB
      | M.null polA = polB
      | M.null polB = polA
      | otherwise   = sumaPol (deleteAt 0 polA) (M.filter (/=0) (insertWith (+) k s polB))
      where (k, s)  = elemAt 0 polA
     
    multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm (n,x) p
      | M.null p    = empty
      | otherwise = insert (k+n) (s*x) (multPorTerm (n,x) (deleteAt 0 p))
      where (k, s) = elemAt 0 p
     
    multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
    multPol polA polB = Prelude.foldl sumaPol empty [ multPorTerm t polB | t <- toList polA]
  3. javjimord
    import 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)]
     
    -- Definiciones alternativas para sumaPol y multPorTerm
     
    sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
    sumaPol p q = M.filter (/=0) $ fromListWith (+) ((toList p) ++ (toList q))
     
    multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
    multPorTerm (n,a) p = M.fromList (zip ((Prelude.map (+n) (keys p))) ((Prelude.map (*a) (elems p))))
     
    multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
    multPol p q = foldl1 (sumaPol) xs
      where xs = [multPorTerm (n,a) q | (n,a) <- toList p]

Leave a Reply

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