Ir al contenido principal

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