Menu Close

Diccionario inverso

José A. Alonso,

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
Posted in Inicial
Tagged , , ,

2 Comments

  1. angruicam1
    Responder 
    import Data.Map   (Map, fromList, fromListWith, toList)
import Data.Tuple (swap)
 
inverso :: (Ord k, Ord v) => Map k v -> Map v [k]
inverso = fromListWith (++) . map (fmap (flip (:) []) . swap) . toList
  2. alerodrod5
    Responder 
     
import Data.Map
 
inverso :: (Ord k, Ord v) => Map k v -> Map v [k]
inverso  = fromListWith(++). Prelude.map f .toList
  where f (a,b) = (b,[a])

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.