Precursor.Data.Map

An efficient implementation of ordered maps from keys to values (dictionaries).

API of this module is strict in both the keys and the values. If you need value-lazy maps, use Data.Map.Lazy instead. The Map type is shared between the lazy and strict modules, meaning that the same Map value can be passed to functions in both modules (although that is rarely needed).

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

 import qualified Data.Map.Strict as Map

The implementation of Map is based on size balanced binary trees (or trees of bounded balance) as described by:

• Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
• J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.

Bounds for union, intersection, and difference are as given by

• Guy Blelloch, Daniel Ferizovic, and Yihan Sun, "Just Join for Parallel Ordered Sets", https://arxiv.org/abs/1602.02120v3.

Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert.

Warning: The size of the map must not exceed maxBound::Int. Violation of this condition is not detected and if the size limit is exceeded, its behaviour is undefined.

Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).

Be aware that the Functor, Traversable and Data instances are the same as for the Data.Map.Lazy module, so if they are used on strict maps, the resulting maps will be lazy.

Documentation

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

A Map from keys k to values a.

Instances

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)

Ord k => IsList (Map k v)

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)

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

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'

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