Data.Map

Please see the documentation of containers for details.

Map type

data Map k a :: * -> * -> *

A Map from keys k to values a.

Instances

Eq2 Map

Since: 0.5.9

Methods

liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> Map a c -> Map b d -> Bool

Ord2 Map

Since: 0.5.9

Methods

liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> Map a c -> Map b d -> Ordering

Show2 Map

Since: 0.5.9

Methods

liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> Map a b -> ShowS

liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [Map a b] -> ShowS

Functor (Map k)

Methods

fmap :: (a -> b) -> Map k a -> Map k b

(<$) :: a -> Map k b -> Map k a

Foldable (Map k)

Methods

fold :: Monoid m => Map k m -> m

foldMap :: Monoid m => (a -> m) -> Map k a -> m

foldr :: (a -> b -> b) -> b -> Map k a -> b

foldr' :: (a -> b -> b) -> b -> Map k a -> b

foldl :: (b -> a -> b) -> b -> Map k a -> b

foldl' :: (b -> a -> b) -> b -> Map k a -> b

foldr1 :: (a -> a -> a) -> Map k a -> a

foldl1 :: (a -> a -> a) -> Map k a -> a

toList :: Map k a -> [a]

null :: Map k a -> Bool

length :: Map k a -> Int

elem :: Eq a => a -> Map k a -> Bool

maximum :: Ord a => Map k a -> a

minimum :: Ord a => Map k a -> a

sum :: Num a => Map k a -> a

product :: Num a => Map k a -> a

Traversable (Map k)

Methods

traverse :: Applicative f => (a -> f b) -> Map k a -> f (Map k b)

sequenceA :: Applicative f => Map k (f a) -> f (Map k a)

mapM :: Monad m => (a -> m b) -> Map k a -> m (Map k b)

sequence :: Monad m => Map k (m a) -> m (Map k a)

Eq k => Eq1 (Map k)

Since: 0.5.9

Methods

liftEq :: (a -> b -> Bool) -> Map k a -> Map k b -> Bool

Ord k => Ord1 (Map k)

Since: 0.5.9

Methods

liftCompare :: (a -> b -> Ordering) -> Map k a -> Map k b -> Ordering

(Ord k, Read k) => Read1 (Map k)

Since: 0.5.9

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Map k a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Map k a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Map k a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Map k a]

Show k => Show1 (Map k)

Since: 0.5.9

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Map k a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Map k a] -> ShowS

Ord k => IsList (Map k v)

Since: 0.5.6.2

Associated Types

type Item (Map k v) :: *

Methods

fromList :: [Item (Map k v)] -> Map k v

fromListN :: Int -> [Item (Map k v)] -> Map k v

toList :: Map k v -> [Item (Map k v)]

(Eq k, Eq a) => Eq (Map k a)

Methods

(==) :: Map k a -> Map k a -> Bool

(/=) :: Map k a -> Map k a -> Bool

(Data k, Data a, Ord k) => Data (Map k a)

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Map k a -> c (Map k a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Map k a)

toConstr :: Map k a -> Constr

dataTypeOf :: Map k a -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c (Map k a))

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Map k a))

gmapT :: (forall b. Data b => b -> b) -> Map k a -> Map k a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Map k a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Map k a -> r

gmapQ :: (forall d. Data d => d -> u) -> Map k a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Map k a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Map k a -> m (Map k a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Map k a -> m (Map k a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Map k a -> m (Map k a)

(Ord k, Ord v) => Ord (Map k v)

Methods

compare :: Map k v -> Map k v -> Ordering

(<) :: Map k v -> Map k v -> Bool

(<=) :: Map k v -> Map k v -> Bool

(>) :: Map k v -> Map k v -> Bool

(>=) :: Map k v -> Map k v -> Bool

max :: Map k v -> Map k v -> Map k v

min :: Map k v -> Map k v -> Map k v

(Ord k, Read k, Read e) => Read (Map k e)

Methods

readsPrec :: Int -> ReadS (Map k e)

readList :: ReadS [Map k e]

readPrec :: ReadPrec (Map k e)

readListPrec :: ReadPrec [Map k e]

(Show k, Show a) => Show (Map k a)

Methods

showsPrec :: Int -> Map k a -> ShowS

show :: Map k a -> String

showList :: [Map k a] -> ShowS

Ord k => Semigroup (Map k v)

Methods

(<>) :: Map k v -> Map k v -> Map k v

sconcat :: NonEmpty (Map k v) -> Map k v

stimes :: Integral b => b -> Map k v -> Map k v

Ord k => Monoid (Map k v)

Methods

mempty :: Map k v

mappend :: Map k v -> Map k v -> Map k v

mconcat :: [Map k v] -> Map k v

(NFData k, NFData a) => NFData (Map k a)

Methods

rnf :: Map k a -> ()

type Item (Map k v)

type Item (Map k v) = (k, v)

Construction

empty :: Map k a

O(1). The empty map.

empty      == fromList []
size empty == 0

singleton :: k -> a -> Map k a

O(1). A map with a single element.

singleton 1 'a'        == fromList [(1, 'a')]
size (singleton 1 'a') == 1

fromSet :: (k -> a) -> Set k -> Map k a

O(n). Build a map from a set of keys and a function which for each key computes its value.

fromSet (\k -> replicate k 'a') (Data.Set.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]
fromSet undefined Data.Set.empty == empty

Insertion

insert :: Ord k => k -> a -> Map k a -> Map k a

O(log n). Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. insert is equivalent to insertWith const.

insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
insert 5 'x' empty                         == singleton 5 'x'

Deletion/Update

delete :: Ord k => k -> Map k a -> Map k a

O(log n). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.

delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
delete 5 empty                         == empty

Query

Lookup

lookup :: Ord k => k -> Map k a -> Maybe a

O(log n). Lookup the value at a key in the map.

The function will return the corresponding value as (Just value), or Nothing if the key isn't in the map.

An example of using lookup:

import Prelude hiding (lookup)
import Data.Map

employeeDept = fromList([("John","Sales"), ("Bob","IT")])
deptCountry = fromList([("IT","USA"), ("Sales","France")])
countryCurrency = fromList([("USA", "Dollar"), ("France", "Euro")])

employeeCurrency :: String -> Maybe String
employeeCurrency name = do
    dept <- lookup name employeeDept
    country <- lookup dept deptCountry
    lookup country countryCurrency

main = do
    putStrLn $ "John's currency: " ++ (show (employeeCurrency "John"))
    putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))

The output of this program:

  John's currency: Just "Euro"
  Pete's currency: Nothing

member :: Ord k => k -> Map k a -> Bool

O(log n). Is the key a member of the map? See also notMember.

member 5 (fromList [(5,'a'), (3,'b')]) == True
member 1 (fromList [(5,'a'), (3,'b')]) == False

Size

null :: Map k a -> Bool

O(1). Is the map empty?

Data.Map.null (empty)           == True
Data.Map.null (singleton 1 'a') == False

Combine

Union

union :: Ord k => Map k a -> Map k a -> Map k a

O(m*log(n/m + 1)), m <= n. The expression (union t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered, i.e. (union == unionWith const).

union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]

Difference

difference :: Ord k => Map k a -> Map k b -> Map k a

O(m*log(n/m + 1)), m <= n. Difference of two maps. Return elements of the first map not existing in the second map.

difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"

Intersection

intersection :: Ord k => Map k a -> Map k b -> Map k a

O(m*log(n/m + 1)), m <= n. Intersection of two maps. Return data in the first map for the keys existing in both maps. (intersection m1 m2 == intersectionWith const m1 m2).

intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"

Lists

Ordered lists

split :: Ord k => k -> Map k a -> (Map k a, Map k a)

O(log n). The expression (split k map) is a pair (map1,map2) where the keys in map1 are smaller than k and the keys in map2 larger than k. Any key equal to k is found in neither map1 nor map2.

split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")])
split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a")
split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty)
split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)