Mini.Data.Map

A structure mapping unique keys to values

Type

data Map k a

A map from keys k to values a, internally structured as an AVL tree

Instances

Foldable (Map k)

Defined in Mini.Data.Map

Methods

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

foldMap :: Monoid m => (a -> m) -> Map k a -> 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)

Defined in Mini.Data.Map

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)

Functor (Map k)

Defined in Mini.Data.Map

Methods

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

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

Ord k => Monoid (Map k a)

Defined in Mini.Data.Map

Methods

mempty :: Map k a

mappend :: Map k a -> Map k a -> Map k a

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

Ord k => Semigroup (Map k a)

Defined in Mini.Data.Map

Methods

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

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

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

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

Defined in Mini.Data.Map

Methods

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

show :: Map k a -> String

showList :: [Map k a] -> ShowS

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

Defined in Mini.Data.Map

Methods

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

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

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

Defined in Mini.Data.Map

Methods

compare :: Map k a -> Map k a -> Ordering

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

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

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

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

max :: Map k a -> Map k a -> Map k a

min :: Map k a -> Map k a -> Map k a

Primitive Recursion

map

Arguments

:: b

Value yielded in case of empty node

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

Function applied in case of non-empty node: left child, key, value, right child, left recursion, right recursion (keys are lesser to the left, greater to the right)

-> Map k a

Object of the case analysis

-> b

Primitive recursion on maps (internally structured as trees)

Construction

empty :: Map k a

O(1) The empty map

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

O(1) Make a map with a single bin

fromList :: Ord k => [(k, a)] -> Map k a

O(n log n) Make a map from a tail-biased list of (key, value) pairs

fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a

O(n log n) Make a map from a list of pairs, combining matching keys

fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a

O(n log n) Make a map from a list of pairs, combining matching keys

fromAscList :: Eq k => [(k, a)] -> Map k a

O(n) Make a map from a tail-biased list of key-sorted pairs

fromAscListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a

O(n) Make a map from a list of key-sorted pairs, combining matching keys

fromAscListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a

O(n) Make a map from a list of key-sorted pairs, combining matching keys

fromDescList :: Eq k => [(k, a)] -> Map k a

O(n) Make a map from a tail-biased list of key-sorted pairs

fromDescListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a

O(n) Make a map from a list of key-sorted pairs, combining matching keys

fromDescListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a

O(n) Make a map from a list of key-sorted pairs, combining matching keys

fromDistinctAscList :: [(k, a)] -> Map k a

O(n) Make a map from a sorted list of key-distinct pairs

fromDistinctDescList :: [(k, a)] -> Map k a

O(n) Make a map from a sorted list of key-distinct pairs

Combination

compose :: Ord b => Map b c -> Map a b -> Map a c

O(n log m) Compose the keys of one set with the values of another

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

O(m log n) Subtract a map by another via key matching

differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a

O(m log n) Subtract a map by another, updating bins of matching keys

differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a

O(m log n) Subtract a map by another, updating bins of matching keys

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

O(n log m) Intersect a map with another via left-biased key matching

intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c

O(n log m) Intersect a map with another by key matching, combining values

intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c

O(n log m) Intersect a map with another by key matching, combining values

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

O(m log n) Unite a map with another via left-biased key matching

unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a

O(m log n) Unite a map with another, combining values of matching keys

unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a

O(m log n) Unite a map with another, combining values of matching keys

unions :: (Foldable t, Ord k) => t (Map k a) -> Map k a

Unite a collection of maps via left-biased key matching

unionsWith :: (Foldable t, Ord k) => (a -> a -> a) -> t (Map k a) -> Map k a

Unite a collection of maps, combining values of matching keys

unionsWithKey :: (Foldable t, Ord k) => (k -> a -> a -> a) -> t (Map k a) -> Map k a

Unite a collection of maps, combining values of matching keys

Conversion

toAscList :: Map k a -> [(k, a)]

O(n) Turn a map into a list of (key, value) pairs in ascending order

toDescList :: Map k a -> [(k, a)]

O(n) Turn a map into a list of (key, value) pairs in descending order

Fold

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

O(n) Reduce a map with a left-associative operation and an accumulator

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

O(n) Reduce a map with a right-associative operation and an accumulator

Modification

adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a

O(log n) Adjust with an operation the value of a key in a map

adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a

O(log n) Adjust with an operation the value of a key in a map

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

O(log n) Adjust with an operation the value of the maximum key in a map

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

O(log n) Adjust with an operation the value of the maximum key in a map

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

O(log n) Adjust with an operation the value of the minimum key in a map

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

O(log n) Adjust with an operation the value of the minimum key in a map

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

O(log n) Delete a key from a map

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

O(log n) Delete the maximum key from a map

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

O(log n) Delete the minimum key from a map

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

O(n) Keep the bins whose values satisfy a predicate

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

O(n) Keep the bins whose keys and values satisfy a predicate

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

O(log n) Insert a key and its value into a map, overwriting if present

insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a

O(log n) Insert a key and its value, combining new and old if present

insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a

O(log n) Insert a key and its value, combining new and old if present

update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a

O(log n) Modify the value of a key or delete its bin with an operation

updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a

O(log n) Modify the value of a key or delete its bin with an operation

updateMax :: Ord k => (a -> Maybe a) -> Map k a -> Map k a

O(log n) Modify the value of the maximum key or delete its bin

updateMaxWithKey :: Ord k => (k -> a -> Maybe a) -> Map k a -> Map k a

O(log n) Modify the value of the maximum key or delete its bin

updateMin :: Ord k => (a -> Maybe a) -> Map k a -> Map k a

O(log n) Modify the value of the minimum key or delete its bin

updateMinWithKey :: Ord k => (k -> a -> Maybe a) -> Map k a -> Map k a

O(log n) Modify the value of the minimum key or delete its bin

Partition

partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)

O(n) Partition a map with a predicate into (true, false) submaps

partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)

O(n) Partition a map with a predicate into (true, false) submaps

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

O(n) Split a map by a key into (lt, eq, gt) submaps

splitMax :: Ord k => Map k a -> Maybe ((k, a), Map k a)

O(log n) Split a map by its maximum key

splitMin :: Ord k => Map k a -> Maybe ((k, a), Map k a)

O(log n) Split a map by its minimum key

Query

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

O(m log n) Check whether two maps have no keys in common

isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool

O(n log m) Check whether the bins of one map exist in the other

isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool

O(n log m) Check if the bins of one map exist in the other by combination

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

O(log n) Fetch the value of a key in a map, or Nothing if absent

lookupGE :: Ord k => k -> Map k a -> Maybe (k, a)

O(log n) Fetch the least bin greater than or equal to a key

lookupGT :: Ord k => k -> Map k a -> Maybe (k, a)

O(log n) Fetch the least bin strictly greater than a key

lookupLE :: Ord k => k -> Map k a -> Maybe (k, a)

O(log n) Fetch the greatest bin less than or equal to a key

lookupLT :: Ord k => k -> Map k a -> Maybe (k, a)

O(log n) Fetch the greatest bin strictly less than a key

lookupMax :: Map k a -> Maybe (k, a)

O(log n) Fetch the bin with the maximum key, or Nothing if empty

lookupMin :: Map k a -> Maybe (k, a)

O(log n) Fetch the bin with the minimum key, or Nothing if empty

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

O(log n) Check whether a key is in a map

null :: Map k a -> Bool

O(1) Check whether a map is empty

size :: Map k a -> Int

O(n) Get the size of a map

Traversal

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

O(n) Apply an operation across a map, transforming its values

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

O(n) Lift a map with a lifting operation on keys and values

Validation

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

O(n^2) Check whether a map is internally height-balanced and ordered

Examples

fromList: tail-biased means that if a list of (key, value) pairs contains pairs with identical keys, the rightmost one is kept.

>>> fromList [('a',1),('b',2),('c',3),('b',4),('a',5)]
[('a',5),('b',4),('c',3)]

fromListWith, fromListWithKey: If a list of (key, value) pairs contains pairs with identical keys, the leftmost one is inserted as is and the subsequent ones adjust the value with the combining function left-associatively. The combining function takes the new value as the left operand, and the existing value as the right operand.

>>> fromListWith (<>) [(1,"a"),(2,"b"),(1,"c"),(1,"d")]
[(1,"dca"),(2,"b")]
>>> let f k new old = old <> ", " <> show k <> new
>>> fromListWithKey f [(1,"a"),(2,"b"),(1,"c"),(1,"d")]
[(1,"a, 1c, 1d"),(2,"b")]

intersection, union, unions: left-biased means that if the operands contain bins with identical keys, the bins from the left operand is kept.

>>> fromList [('a',1),('b',2)] `intersection` fromList [('c',3),('b',4),('a',5)]
[('a',1),('b',2)]
>>> fromList [('a',1),('b',2)] `union` fromList [('c',3),('b',4),('a',5)]
[('a',1),('b',2),('c',3)]

insertWith, insertWithKey: If the key does not exist in the map, it is inserted with the given value as is. Otherwise, the existing value is adjusted with the combining function, which takes the given value as the left operand and the existing value as the right operand.

>>> insertWith (<>) 1 "foo" $ fromList [(2,"bar"),(3,"baz")]
[(1,"foo"),(2,"bar"),(3,"baz")]
>>> insertWith (<>) 2 "foo" $ fromList [(2,"bar"),(3,"baz")]
[(2,"foobar"),(3,"baz")]
>>> let f k new old = k + new - old
>>> insertWithKey f 1 2 $ fromList [(2,3),(3,5)]
[(1,2),(2,3),(3,5)]
>>> insertWithKey f 2 7 $ fromList [(2,3),(3,5)]
[(2,6),(3,5)]

update: If the key does not exist, the map is unchanged. If the key exists and the result of the operation is Just x, the value of the corresponding bin is updated to x. If the key exists and the result of the operation is Nothing, the corresponding bin is removed.

>>> f a = if a == 2 then Just 9 else Nothing
>>> update f 'c' $ fromList [('a',1),('b',2)]
[('a',1),('b',2)]
>>> update f 'b' $ fromList [('a',1),('b',2)]
[('a',1),('b',9)]
>>> update f 'a' $ fromList [('a',1),('b',2)]
[('b',2)]