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
[("a",3),("b",2),("c",3),("d",2),("e",1)])
es
[(1,["e"]),(2,["d","b"]),(3,["c","a"])]
Definir la función
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])]
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