Safe Haskell	Safe
Language	Haskell2010

Precursor.Data.Map

Description

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.

Synopsis

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