Diccionario inverso
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
|
1 |
[("a",3),("b",2),("c",3),("d",2),("e",1)]) |
es
|
1 |
[(1,["e"]),(2,["d","b"]),(3,["c","a"])] |
Definir la función
|
1 |
inverso :: (Ord k, Ord v) => Map k v -> Map v [k] |
tal que (inverso d) es el inverso del diccionario d. Por ejemplo,
|
1 2 3 4 |
λ> 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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 |