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)]) |
[("a",3),("b",2),("c",3),("d",2),("e",1)])
es
[(1,["e"]),(2,["d","b"]),(3,["c","a"])] |
[(1,["e"]),(2,["d","b"]),(3,["c","a"])]
Definir la función
inverso :: (Ord k, Ord v) => Map k v -> Map v [k] |
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
Se puede imprimir o compartir con
2 Comments