Diccionarios

Operaciones con polinomios como diccionarios

PorJosé A. Alonso 15-mayo-202022-mayo-2020

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

1	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

1 2	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)]

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

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)]

λ> 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)]

1 2	λ> 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)]

λ> 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

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

Diccionario inverso

PorJosé A. Alonso 26-abril-20187-mayo-2018

El inverso de un diccionario d es el diccionario que a cada valor x le asigna la lista de claves cuyo valor en d es x. Por ejemplo, el inverso de

   [("a",3),("b",2),("c",3),("d",2),("e",1)])

1	[("a",3),("b",2),("c",3),("d",2),("e",1)])

   [(1,["e"]),(2,["d","b"]),(3,["c","a"])]

1	[(1,["e"]),(2,["d","b"]),(3,["c","a"])]

Definir la función

   inverso :: (Ord k, Ord v) => Map k v -> Map v [k]

1	inverso :: (Ord k, Ord v) => Map k v -> Map v [k]

tal que (inverso d) es el inverso del diccionario d. Por ejemplo,

   λ> inverso (fromList [("a",3),("b",2),("c",3),("d",2),("e",1)])
   fromList [(1,["e"]),(2,["d","b"]),(3,["c","a"])]
   λ> inverso (fromList [(x,x^2) | x <- [-3,-2..3]])
   fromList [(0,[0]),(1,[1,-1]),(4,[2,-2]),(9,[3,-3])]

λ> inverso (fromList [("a",3),("b",2),("c",3),("d",2),("e",1)])

fromList [(1,["e"]),(2,["d","b"]),(3,["c","a"])]

λ> inverso (fromList [(x,x^2) | x <- [-3,-2..3]])

fromList [(0,[0]),(1,[1,-1]),(4,[2,-2]),(9,[3,-3])]

Soluciones

import Data.Map ( Map
                , assocs
                , deleteFindMin
                , empty
                , fromList
                , fromListWith
                , insertWith
                )
import qualified Data.Map as M 


-- 1ª definición
inverso :: (Ord k, Ord v) => Map k v -> Map v [k]
inverso d = fromListWith (++) [(y,[x]) | (x,y) <- assocs d]

-- 2ª definición
inverso2 :: (Ord k, Ord v) => Map k v -> Map v [k]
inverso2 d
  | M.null d  = empty
  | otherwise = insertWith (++) y [x] (inverso2 e)
  where ((x,y),e) = deleteFindMin d

import Data.Map ( Map

, assocs

, deleteFindMin

, empty

, fromList

, fromListWith

, insertWith

)

import qualified Data.Map as M

-- 1ª definición

inverso :: (Ord k, Ord v) => Map k v -> Map v [k]

inverso d = fromListWith (++) [(y,[x]) | (x,y) <- assocs d]

-- 2ª definición

inverso2 :: (Ord k, Ord v) => Map k v -> Map v [k]

inverso2 d

| M.null d = empty

| otherwise = insertWith (++) y [x] (inverso2 e)

where ((x,y),e) = deleteFindMin d

Operaciones con polinomios como diccionarios

PorJosé A. Alonso 20-abril-201725-abril-2021

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

1	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

1 2	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)]

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

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)]

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)]

1 2	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)]

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

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

Agrupamiento según valores

PorJosé A. Alonso 5-abril-201712-abril-2017

Definir la función

   agrupa :: Ord c => (a -> c) -> [a] -> Map c [a]

1	agrupa :: Ord c => (a -> c) -> [a] -> Map c [a]

tal que (agrupa f xs) es el diccionario obtenido agrupando los elementos de xs según sus valores mediante la función f. Por ejemplo,

   ghci> agrupa length ["hoy", "ayer", "ana", "cosa"]
   fromList [(3,["hoy","ana"]),(4,["ayer","cosa"])]
   ghci> agrupa head ["claro", "ayer", "ana", "cosa"]
   fromList [('a',["ayer","ana"]),('c',["claro","cosa"])]

ghci> agrupa length ["hoy", "ayer", "ana", "cosa"]

fromList [(3,["hoy","ana"]),(4,["ayer","cosa"])]

ghci> agrupa head ["claro", "ayer", "ana", "cosa"]

fromList [('a',["ayer","ana"]),('c',["claro","cosa"])]

Soluciones

import qualified Data.List as L
import Data.Map

-- 1ª definición (por recursión)
agrupa1 :: Ord c => (a -> c) -> [a] -> Map c [a]
agrupa1 _ []     = empty
agrupa1 f (x:xs) = insertWith (++) (f x) [x] (agrupa1 f xs)

-- 2ª definición (por plegado)
agrupa2 :: Ord c => (a -> c) -> [a] -> Map c [a]
agrupa2 f = L.foldr (\x -> insertWith (++) (f x) [x]) empty

import qualified Data.List as L

import Data.Map

-- 1ª definición (por recursión)

agrupa1 :: Ord c => (a -> c) -> [a] -> Map c [a]

agrupa1 _ [] = empty

agrupa1 f (x:xs) = insertWith (++) (f x) [x] (agrupa1 f xs)

-- 2ª definición (por plegado)

agrupa2 :: Ord c => (a -> c) -> [a] -> Map c [a]

agrupa2 f = L.foldr (\x -> insertWith (++) (f x) [x]) empty

Distancias entre primos consecutivos

PorJosé A. Alonso 4-abril-201711-abril-2017

Los 15 primeros números primos son

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Las distancias entre los elementos consecutivos son

   1, 2, 2, 4, 2,  4,  2,  4,  6,  2,  6,  4,  2,  4

1	1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4

La distribución de las distancias es

   (1,1), (2,6), (4,5), (6,2)

1	(1,1), (2,6), (4,5), (6,2)

(es decir, el 1 aparece una vez, el 2 aparece 6 veces, etc.) La frecuencia de las distancias es

   (1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

1	(1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

(es decir, el 1 aparece el 7.142857%, el 2 el 42.857143% etc.)

Definir las funciones

  cuentaDistancias        :: Int -> [(Int,Int)]
  frecuenciasDistancias   :: Int -> [(Int,Float)]
  graficas                :: [Int] -> IO ()
  distanciasMasFrecuentes :: Int -> [Int]

cuentaDistancias :: Int -> [(Int,Int)]

frecuenciasDistancias :: Int -> [(Int,Float)]

graficas :: [Int] -> IO ()

distanciasMasFrecuentes :: Int -> [Int]

tales que

(cuentaDistancias n) es la distribución de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> cuentaDistancias 15
     [(1,1),(2,6),(4,5),(6,2)]
     λ> cuentaDistancias 100
     [(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

λ> cuentaDistancias 15

[(1,1),(2,6),(4,5),(6,2)]

λ> cuentaDistancias 100

[(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

(frecuenciasDistancias n) es la frecuencia de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> frecuenciasDistancias 15
     [(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]
     λ> frecuenciasDistancias 30
     [(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

λ> frecuenciasDistancias 15

[(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]

λ> frecuenciasDistancias 30

[(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

(graficas ns) dibuja las gráficas de (frecuenciasDistancias k) para k en ns. Por ejemplo, (graficas [10,20,30]) dibuja

(graficas [1000,2000,3000]) dibuja

y (graficas [100000,200000,300000]) dibuja
(distanciasMasFrecuentes n) es la lista de las distancias más frecuentes entre los elementos consecutivos de la lista de los n primeros primos. Por ejemplo,

     distanciasMasFrecuentes 15     ==  [2]
     distanciasMasFrecuentes 26     ==  [2,4]
     distanciasMasFrecuentes 32     ==  [4]
     distanciasMasFrecuentes 41     ==  [2,4,6]
     distanciasMasFrecuentes 77     ==  [6]
     distanciasMasFrecuentes 160    ==  [4,6]
     distanciasMasFrecuentes (10^6) == [6]

distanciasMasFrecuentes 15 == [2]

distanciasMasFrecuentes 26 == [2,4]

distanciasMasFrecuentes 32 == [4]

distanciasMasFrecuentes 41 == [2,4,6]

distanciasMasFrecuentes 77 == [6]

distanciasMasFrecuentes 160 == [4,6]

distanciasMasFrecuentes (10^6) == [6]

Comprobar con QuickCheck si para todo n > 160 se verifica que (distanciasMasFrecuentes n) es [6].

Soluciones

import Data.Numbers.Primes
import qualified Data.Map as M 
import Graphics.Gnuplot.Simple
import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]
cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int
dicDistancias n =
  M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]
distancias n =
  zipWith (-) (tail xs) xs
  where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]
frecuenciasDistancias n =
  [(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]
  where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()
graficas ns =
  plotLists [Key Nothing]
            (map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]
distanciasMasFrecuentes n =
  M.keys (M.filter (==m) d)
  where d = dicDistancias n
        m = maximum (M.elems d)

-- La propiedad es
prop_distanciasMasFrecuentes :: Int -> Bool
prop_distanciasMasFrecuentes n =
  distanciasMasFrecuentes (161 + abs n) == [6]

import Data.Numbers.Primes

import qualified Data.Map as M

import Graphics.Gnuplot.Simple

import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]

cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int

dicDistancias n =

M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]

distancias n =

zipWith (-) (tail xs) xs

where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]

frecuenciasDistancias n =

[(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]

where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()

graficas ns =

plotLists [Key Nothing]

(map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]

distanciasMasFrecuentes n =

M.keys (M.filter (==m) d)

where d = dicDistancias n

m = maximum (M.elems d)

-- La propiedad es

prop_distanciasMasFrecuentes :: Int -> Bool

prop_distanciasMasFrecuentes n =

distanciasMasFrecuentes (161 + abs n) == [6]

Agrupamiento según valores

PorJosé A. Alonso 29-abril-201525-abril-2021

Definir la función

   agrupa :: Ord c => (a -> c) -> [a] -> Map c [a]

1	agrupa :: Ord c => (a -> c) -> [a] -> Map c [a]

tal que (agrupa f xs) es el diccionario obtenido agrupando los elementos de xs según sus valores mediante la función f. Por ejemplo,

   ghci> agrupa length ["hoy", "ayer", "ana", "cosa"]
   fromList [(3,["hoy","ana"]),(4,["ayer","cosa"])]
   ghci> agrupa head ["claro", "ayer", "ana", "cosa"]
   fromList [('a',["ayer","ana"]),('c',["claro","cosa"])]
   ghci> agrupa length (words "suerte en el examen")
   fromList [(2,["en","el"]),(6,["suerte","examen"])]

ghci> agrupa length ["hoy", "ayer", "ana", "cosa"]

fromList [(3,["hoy","ana"]),(4,["ayer","cosa"])]

ghci> agrupa head ["claro", "ayer", "ana", "cosa"]

fromList [('a',["ayer","ana"]),('c',["claro","cosa"])]

ghci> agrupa length (words "suerte en el examen")

fromList [(2,["en","el"]),(6,["suerte","examen"])]

Soluciones

import qualified Data.List as L
import Data.Map

-- 1ª definición (por recursión)
agrupa1 :: Ord c => (a -> c) -> [a] -> Map c [a]
agrupa1 _ []     = empty
agrupa1 f (x:xs) = insertWith (++) (f x) [x] (agrupa1 f xs)

-- 2ª definición (por plegado)
agrupa2 :: Ord c => (a -> c) -> [a] -> Map c [a]
agrupa2 f = L.foldr (\x -> insertWith (++) (f x) [x]) empty

import qualified Data.List as L

import Data.Map

-- 1ª definición (por recursión)

agrupa1 :: Ord c => (a -> c) -> [a] -> Map c [a]

agrupa1 _ [] = empty

agrupa1 f (x:xs) = insertWith (++) (f x) [x] (agrupa1 f xs)

-- 2ª definición (por plegado)

agrupa2 :: Ord c => (a -> c) -> [a] -> Map c [a]

agrupa2 f = L.foldr (\x -> insertWith (++) (f x) [x]) empty

Operaciones con polinomios como diccionarios

Soluciones

Diccionario inverso

Soluciones

Operaciones con polinomios como diccionarios

Soluciones

Agrupamiento según valores

Soluciones

Distancias entre primos consecutivos

Soluciones

Agrupamiento según valores

Soluciones

Entradas recientes

Buscar

Correo electrónico