- class (Repr k, TrieKey (Rep k)) => TKey k
- data TMap k a
- data TLocation k a
- key :: TKey k => TLocation k a -> k
- before :: TKey k => TLocation k a -> TMap k a
- beforeWith :: TKey k => a -> TLocation k a -> TMap k a
- after :: TKey k => TLocation k a -> TMap k a
- afterWith :: TKey k => a -> TLocation k a -> TMap k a
- search :: TKey k => k -> TMap k a -> (Maybe a, TLocation k a)
- index :: TKey k => Int -> TMap k a -> (a, TLocation k a)
- minLocation :: TKey k => TMap k a -> Maybe (a, TLocation k a)
- maxLocation :: TKey k => TMap k a -> Maybe (a, TLocation k a)
- assign :: TKey k => a -> TLocation k a -> TMap k a
- clear :: TKey k => TLocation k a -> TMap k a
- (!) :: TKey k => TMap k a -> k -> a
- (\\) :: TKey k => TMap k a -> TMap k b -> TMap k a
- null :: TKey k => TMap k a -> Bool
- size :: TKey k => TMap k a -> Int
- member :: TKey k => k -> TMap k a -> Bool
- notMember :: TKey k => k -> TMap k a -> Bool
- lookup :: TKey k => k -> TMap k a -> Maybe a
- findWithDefault :: TKey k => a -> k -> TMap k a -> a
- empty :: TKey k => TMap k a
- singleton :: TKey k => k -> a -> TMap k a
- insert :: TKey k => k -> a -> TMap k a -> TMap k a
- insertWith :: TKey k => (a -> a -> a) -> k -> a -> TMap k a -> TMap k a
- insertWithKey :: TKey k => (k -> a -> a -> a) -> k -> a -> TMap k a -> TMap k a
- insertLookupWithKey :: TKey k => (k -> a -> a -> a) -> k -> a -> TMap k a -> (Maybe a, TMap k a)
- delete :: TKey k => k -> TMap k a -> TMap k a
- adjust :: TKey k => (a -> a) -> k -> TMap k a -> TMap k a
- adjustWithKey :: TKey k => (k -> a -> a) -> k -> TMap k a -> TMap k a
- update :: TKey k => (a -> Maybe a) -> k -> TMap k a -> TMap k a
- updateWithKey :: TKey k => (k -> a -> Maybe a) -> k -> TMap k a -> TMap k a
- alter :: TKey k => (Maybe a -> Maybe a) -> k -> TMap k a -> TMap k a
- union :: TKey k => TMap k a -> TMap k a -> TMap k a
- unionWith :: TKey k => (a -> a -> a) -> TMap k a -> TMap k a -> TMap k a
- unionWithKey :: TKey k => (k -> a -> a -> a) -> TMap k a -> TMap k a -> TMap k a
- unionMaybeWith :: TKey k => (a -> a -> Maybe a) -> TMap k a -> TMap k a -> TMap k a
- unionMaybeWithKey :: TKey k => (k -> a -> a -> Maybe a) -> TMap k a -> TMap k a -> TMap k a
- symmetricDifference :: TKey k => TMap k a -> TMap k a -> TMap k a
- difference :: TKey k => TMap k a -> TMap k b -> TMap k a
- differenceWith :: TKey k => (a -> b -> Maybe a) -> TMap k a -> TMap k b -> TMap k a
- differenceWithKey :: TKey k => (k -> a -> b -> Maybe a) -> TMap k a -> TMap k b -> TMap k a
- intersection :: TKey k => TMap k a -> TMap k b -> TMap k a
- intersectionWith :: TKey k => (a -> b -> c) -> TMap k a -> TMap k b -> TMap k c
- intersectionWithKey :: TKey k => (k -> a -> b -> c) -> TMap k a -> TMap k b -> TMap k c
- intersectionMaybeWith :: TKey k => (a -> b -> Maybe c) -> TMap k a -> TMap k b -> TMap k c
- intersectionMaybeWithKey :: TKey k => (k -> a -> b -> Maybe c) -> TMap k a -> TMap k b -> TMap k c
- map :: TKey k => (a -> b) -> TMap k a -> TMap k b
- mapWithKey :: TKey k => (k -> a -> b) -> TMap k a -> TMap k b
- mapKeys :: (TKey k, TKey k') => (k -> k') -> TMap k a -> TMap k' a
- mapKeysWith :: (TKey k, TKey k') => (a -> a -> a) -> (k -> k') -> TMap k a -> TMap k' a
- mapKeysMonotonic :: (TKey k, TKey k') => (k -> k') -> TMap k a -> TMap k' a
- traverseWithKey :: (TKey k, Applicative f) => (k -> a -> f b) -> TMap k a -> f (TMap k b)
- foldrWithKey :: TKey k => (k -> a -> b -> b) -> b -> TMap k a -> b
- foldlWithKey :: TKey k => (b -> k -> a -> b) -> b -> TMap k a -> b
- keysSet :: TKey k => TMap k a -> TSet k
- elems :: TKey k => TMap k a -> [a]
- keys :: TKey k => TMap k a -> [k]
- assocs :: TKey k => TMap k a -> [(k, a)]
- fromList :: TKey k => [(k, a)] -> TMap k a
- fromListWith :: TKey k => (a -> a -> a) -> [(k, a)] -> TMap k a
- fromListWithKey :: TKey k => (k -> a -> a -> a) -> [(k, a)] -> TMap k a
- elemsVector :: (TKey k, Vector v a) => TMap k a -> v a
- keysVector :: (TKey k, Vector v k) => TMap k a -> v k
- assocsVector :: (TKey k, Vector v (k, a)) => TMap k a -> v (k, a)
- fromVector :: (TKey k, Vector v (k, a)) => v (k, a) -> TMap k a
- fromVectorWith :: (TKey k, Vector v (k, a)) => (a -> a -> a) -> v (k, a) -> TMap k a
- fromVectorWithKey :: (TKey k, Vector v (k, a)) => (k -> a -> a -> a) -> v (k, a) -> TMap k a
- fromAscList :: TKey k => [(k, a)] -> TMap k a
- fromAscListWith :: TKey k => (a -> a -> a) -> [(k, a)] -> TMap k a
- fromAscListWithKey :: TKey k => (k -> a -> a -> a) -> [(k, a)] -> TMap k a
- fromDistinctAscList :: TKey k => [(k, a)] -> TMap k a
- fromAscVector :: (TKey k, Vector v (k, a)) => v (k, a) -> TMap k a
- fromAscVectorWith :: (TKey k, Vector v (k, a)) => (a -> a -> a) -> v (k, a) -> TMap k a
- fromAscVectorWithKey :: (TKey k, Vector v (k, a)) => (k -> a -> a -> a) -> v (k, a) -> TMap k a
- fromDistinctAscVector :: (TKey k, Vector v (k, a)) => v (k, a) -> TMap k a
- filter :: TKey k => (a -> Bool) -> TMap k a -> TMap k a
- filterWithKey :: TKey k => (k -> a -> Bool) -> TMap k a -> TMap k a
- partition :: TKey k => (a -> Bool) -> TMap k a -> (TMap k a, TMap k a)
- partitionWithKey :: TKey k => (k -> a -> Bool) -> TMap k a -> (TMap k a, TMap k a)
- mapMaybe :: TKey k => (a -> Maybe b) -> TMap k a -> TMap k b
- mapMaybeWithKey :: TKey k => (k -> a -> Maybe b) -> TMap k a -> TMap k b
- mapEither :: TKey k => (a -> Either b c) -> TMap k a -> (TMap k b, TMap k c)
- mapEitherWithKey :: TKey k => (k -> a -> Either b c) -> TMap k a -> (TMap k b, TMap k c)
- split :: TKey k => k -> TMap k a -> (TMap k a, TMap k a)
- splitLookup :: TKey k => k -> TMap k a -> (TMap k a, Maybe a, TMap k a)
- isSubmapOf :: (TKey k, Eq a) => TMap k a -> TMap k a -> Bool
- isSubmapOfBy :: TKey k => (a -> b -> Bool) -> TMap k a -> TMap k b -> Bool
- lookupIndex :: TKey k => k -> TMap k a -> Maybe Int
- findIndex :: TKey k => k -> TMap k a -> Int
- elemAt :: TKey k => Int -> TMap k a -> (k, a)
- updateAt :: TKey k => (k -> a -> Maybe a) -> Int -> TMap k a -> TMap k a
- deleteAt :: TKey k => Int -> TMap k a -> TMap k a
- findMin :: TKey k => TMap k a -> (k, a)
- findMax :: TKey k => TMap k a -> (k, a)
- deleteMin :: TKey k => TMap k a -> TMap k a
- deleteMax :: TKey k => TMap k a -> TMap k a
- deleteFindMin :: TKey k => TMap k a -> ((k, a), TMap k a)
- deleteFindMax :: TKey k => TMap k a -> ((k, a), TMap k a)
- updateMin :: TKey k => (a -> Maybe a) -> TMap k a -> TMap k a
- updateMax :: TKey k => (a -> Maybe a) -> TMap k a -> TMap k a
- updateMinWithKey :: TKey k => (k -> a -> Maybe a) -> TMap k a -> TMap k a
- updateMaxWithKey :: TKey k => (k -> a -> Maybe a) -> TMap k a -> TMap k a
- minView :: TKey k => TMap k a -> Maybe (a, TMap k a)
- maxView :: TKey k => TMap k a -> Maybe (a, TMap k a)
- minViewWithKey :: TKey k => TMap k a -> Maybe ((k, a), TMap k a)
- maxViewWithKey :: TKey k => TMap k a -> Maybe ((k, a), TMap k a)
Map type
A map from keys k
to values a
, backed by a trie.
Location type
Components
key :: TKey k => TLocation k a -> kSource
O(1). The key marking the position of the "hole" in the map.
beforeWith :: TKey k => a -> TLocation k a -> TMap k aSource
is equivalent to beforeWith
a loc
.
insert
(key
loc) a (before
loc)
Locations in maps
minLocation :: TKey k => TMap k a -> Maybe (a, TLocation k a)Source
O(log n). Return the value and an updatable location for the
least key in the map, or Nothing
if the map is empty.
Properties:
size
m > 0 ==> let Just (v, loc) =minLocation
i m insize
(before
loc) == 0 &&assign
v loc == m
findMin
m == let Just (v, loc) =minLocation
i m in (key
loc, v)
maxLocation :: TKey k => TMap k a -> Maybe (a, TLocation k a)Source
Return the value and an updatable location for the
greatest key in the map, or Nothing
if the map is empty.
Properties:
size
m > 0 ==> let Just (v, loc) =maxLocation
i m insize
(after
loc) == 0 &&assign
v loc == m
findMax
m == let Just (v, loc) =maxLocation
i m in (key
loc, v)
Building maps
Operators
(!) :: TKey k => TMap k a -> k -> aSource
Find the value at a key. Calls error
when the element can not be found.
Query
size :: TKey k => TMap k a -> IntSource
O(1). The number of elements in the map.
size empty == 0 size (singleton 1 'a') == 1 size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
member :: TKey k => k -> TMap k a -> BoolSource
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
notMember :: TKey k => k -> TMap k a -> BoolSource
Is the key not a member of the map? See also member
.
notMember 5 (fromList [(5,'a'), (3,'b')]) == False notMember 1 (fromList [(5,'a'), (3,'b')]) == True
findWithDefault :: TKey k => a -> k -> TMap k a -> aSource
The expression (
returns the value at key findWithDefault
def k map)k
or returns default value def
when the key is not in the map.
Construction
Insertion
insert :: TKey k => k -> a -> TMap k a -> TMap k aSource
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'
insertWith :: TKey k => (a -> a -> a) -> k -> a -> TMap k a -> TMap k aSource
Insert with a function, combining new value and old value.
will insert the pair (key, value) into insertWith
f key value mpmp
if key does
not exist in the map. If the key does exist, the function will
insert the pair (key, f new_value old_value)
.
insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")] insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")] insertWith (++) 5 "xxx" empty == singleton 5 "xxx"
insertWithKey :: TKey k => (k -> a -> a -> a) -> k -> a -> TMap k a -> TMap k aSource
Insert with a function, combining key, new value and old value.
will insert the pair (key, value) into insertWithKey
f key value mpmp
if key does
not exist in the map. If the key does exist, the function will
insert the pair (key,f key new_value old_value)
.
Note that the key passed to f is the same key passed to insertWithKey
.
let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")] insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")] insertWithKey f 5 "xxx" empty == singleton 5 "xxx"
insertLookupWithKey :: TKey k => (k -> a -> a -> a) -> k -> a -> TMap k a -> (Maybe a, TMap k a)Source
Combines insert operation with old value retrieval.
The expression (
)
is a pair where the first element is equal to (insertLookupWithKey
f k x map
)
and the second element equal to (lookup
k map
).
insertWithKey
f k x map
let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")]) insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "xxx")]) insertLookupWithKey f 5 "xxx" empty == (Nothing, singleton 5 "xxx")
Delete/Update
delete :: TKey k => k -> TMap k a -> TMap k aSource
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
adjust :: TKey k => (a -> a) -> k -> TMap k a -> TMap k aSource
Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.
adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")] adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] adjust ("new " ++) 7 empty == empty
adjustWithKey :: TKey k => (k -> a -> a) -> k -> TMap k a -> TMap k aSource
Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.
let f key x = (show key) ++ ":new " ++ x adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")] adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] adjustWithKey f 7 empty == empty
update :: TKey k => (a -> Maybe a) -> k -> TMap k a -> TMap k aSource
The expression (
) updates the value update
f k mapx
at k
(if it is in the map). If (f x
) is Nothing
, the element is
deleted. If it is (
), the key Just
yk
is bound to the new value y
.
let f x = if x == "a" then Just "new a" else Nothing update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")] update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
updateWithKey :: TKey k => (k -> a -> Maybe a) -> k -> TMap k a -> TMap k aSource
The expression (
) updates the
value updateWithKey
f k mapx
at k
(if it is in the map). If (f k x
) is Nothing
,
the element is deleted. If it is (
), the key Just
yk
is bound
to the new value y
.
let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")] updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
Combine
Union
union :: TKey k => TMap k a -> TMap k a -> TMap k aSource
The expression (
) takes the left-biased union of union
t1 t2t1
and t2
.
It prefers t1
when duplicate keys are encountered,
i.e. (
).
The implementation uses the efficient hedge-union algorithm.
Hedge-union is more efficient on (bigset `union
== unionWith
const
union
` smallset).
union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
unionWith :: TKey k => (a -> a -> a) -> TMap k a -> TMap k a -> TMap k aSource
O(n+m). Union with a combining function. The implementation uses the efficient hedge-union algorithm.
unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
unionMaybeWith :: TKey k => (a -> a -> Maybe a) -> TMap k a -> TMap k a -> TMap k aSource
Union with a combining function. The implementation uses the efficient hedge-union algorithm.
unionMaybeWithKey :: TKey k => (k -> a -> a -> Maybe a) -> TMap k a -> TMap k a -> TMap k aSource
Union with a combining function. The implementation uses the efficient hedge-union algorithm.
Hedge-union is more efficient on (bigset `union
` smallset).
let f key left_value right_value = Just ((show key) ++ ":" ++ left_value ++ "|" ++ right_value) unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
symmetricDifference :: TKey k => TMap k a -> TMap k a -> TMap k aSource
symmetricDifference
is equivalent to
.
unionMaybeWith
( _ _ -> Nothing)
Difference
difference :: TKey k => TMap k a -> TMap k b -> TMap k aSource
Difference of two maps. Return elements of the first map not existing in the second map. The implementation uses an efficient hedge algorithm comparable with hedge-union.
difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
differenceWith :: TKey k => (a -> b -> Maybe a) -> TMap k a -> TMap k b -> TMap k aSource
Difference with a combining function.
When two equal keys are
encountered, the combining function is applied to the values of these keys.
If it returns Nothing
, the element is discarded (proper set difference). If
it returns (
), the element is updated with a new value Just
yy
.
The implementation uses an efficient hedge algorithm comparable with hedge-union.
let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")]) == singleton 3 "b:B"
differenceWithKey :: TKey k => (k -> a -> b -> Maybe a) -> TMap k a -> TMap k b -> TMap k aSource
Difference with a combining function. When two equal keys are
encountered, the combining function is applied to the key and both values.
If it returns Nothing
, the element is discarded (proper set difference). If
it returns (
), the element is updated with a new value Just
yy
.
The implementation uses an efficient hedge algorithm comparable with hedge-union.
let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")]) == singleton 3 "3:b|B"
Intersection
intersection :: TKey k => TMap k a -> TMap k b -> TMap k aSource
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"
intersectionWith :: TKey k => (a -> b -> c) -> TMap k a -> TMap k b -> TMap k cSource
Intersection with a combining function.
intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
intersectionWithKey :: TKey k => (k -> a -> b -> c) -> TMap k a -> TMap k b -> TMap k cSource
Intersection with a combining function.
Intersection is more efficient on (bigset `intersection
` smallset).
let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"
intersectionMaybeWith :: TKey k => (a -> b -> Maybe c) -> TMap k a -> TMap k b -> TMap k cSource
is equivalent to
intersectionMaybeWith
f m1 m2
.
mapMaybe
id
(intersectionWith
f m1 m2)
intersectionMaybeWithKey :: TKey k => (k -> a -> b -> Maybe c) -> TMap k a -> TMap k b -> TMap k cSource
is equivalent to
intersectionMaybeWithKey
f m1 m2
.
mapMaybe
id
(intersectionWithKey
f m1 m2)
Traversal
Map
map :: TKey k => (a -> b) -> TMap k a -> TMap k bSource
Map a function over all values in the map.
map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
mapWithKey :: TKey k => (k -> a -> b) -> TMap k a -> TMap k bSource
Map a function over all values in the map.
let f key x = (show key) ++ ":" ++ x mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
mapKeys :: (TKey k, TKey k') => (k -> k') -> TMap k a -> TMap k' aSource
is the map obtained by applying mapKeys
f sf
to each key of s
.
The size of the result may be smaller if f
maps two or more distinct
keys to the same new key. In this case the value at the smallest of
these keys is retained.
mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")] mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c" mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
mapKeysWith :: (TKey k, TKey k') => (a -> a -> a) -> (k -> k') -> TMap k a -> TMap k' aSource
is the map obtained by applying mapKeysWith
c f sf
to each key of s
.
The size of the result may be smaller if f
maps two or more distinct
keys to the same new key. In this case the associated values will be
combined using c
.
mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab" mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"
mapKeysMonotonic :: (TKey k, TKey k') => (k -> k') -> TMap k a -> TMap k' aSource
, but works only when mapKeysMonotonic
f s == mapKeys
f sf
is strictly monotonic.
That is, for any values x
and y
, if x
< y
then f x
< f y
.
The precondition is not checked.
Semi-formally, we have:
and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapKeysMonotonic f s == mapKeys f s where ls = keys s
This means that f
maps distinct original keys to distinct resulting keys.
This function has better performance than mapKeys
.
mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
Traverse
traverseWithKey :: (TKey k, Applicative f) => (k -> a -> f b) -> TMap k a -> f (TMap k b)Source
Map each key/element pair to an action, evaluate these actions from left to right, and collect the results.
Fold
foldrWithKey :: TKey k => (k -> a -> b -> b) -> b -> TMap k a -> bSource
Post-order fold. The function will be applied from the lowest value to the highest.
foldlWithKey :: TKey k => (b -> k -> a -> b) -> b -> TMap k a -> bSource
Pre-order fold. The function will be applied from the highest value to the lowest.
Conversion
keysSet :: TKey k => TMap k a -> TSet kSource
The set of all keys of the map.
keysSet (fromList [(5,"a"), (3,"b")]) == Data.TrieSet.fromList [3,5] keysSet empty == Data.TrieSet.empty
Lists
elems :: TKey k => TMap k a -> [a]Source
Return all elements of the map in the ascending order of their keys.
elems (fromList [(5,"a"), (3,"b")]) == ["b","a"] elems empty == []
keys :: TKey k => TMap k a -> [k]Source
Return all keys of the map in ascending order.
keys (fromList [(5,"a"), (3,"b")]) == [3,5] keys empty == []
assocs :: TKey k => TMap k a -> [(k, a)]Source
Return all key/value pairs in the map in ascending key order.
assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")] assocs empty == []
fromList :: TKey k => [(k, a)] -> TMap k aSource
Build a map from a list of key/value pairs. See also fromAscList
.
If the list contains more than one value for the same key, the last value
for the key is retained.
fromList [] == empty fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")] fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
fromListWith :: TKey k => (a -> a -> a) -> [(k, a)] -> TMap k aSource
Build a map from a list of key/value pairs with a combining function. See also fromAscListWith
.
fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")] fromListWith (++) [] == empty
fromListWithKey :: TKey k => (k -> a -> a -> a) -> [(k, a)] -> TMap k aSource
Build a map from a list of key/value pairs with a combining function. See also fromAscListWith
.
fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")] fromListWith (++) [] == empty
Vectors
elemsVector :: (TKey k, Vector v a) => TMap k a -> v aSource
Return all elements of the map in the ascending order of their keys. Does not currently fuse.
keysVector :: (TKey k, Vector v k) => TMap k a -> v kSource
Return all keys of the map in ascending order. Does not currently fuse.
assocsVector :: (TKey k, Vector v (k, a)) => TMap k a -> v (k, a)Source
Return all key/value pairs in the map in ascending key order. Does not currently fuse.
fromVector :: (TKey k, Vector v (k, a)) => v (k, a) -> TMap k aSource
fromVectorWith :: (TKey k, Vector v (k, a)) => (a -> a -> a) -> v (k, a) -> TMap k aSource
Equivalent to
.
fromListWith
f (toList
xs)
fromVectorWithKey :: (TKey k, Vector v (k, a)) => (k -> a -> a -> a) -> v (k, a) -> TMap k aSource
Equivalent to
.
fromListWithKey
f (toList
xs)
Ordered lists
fromAscList :: TKey k => [(k, a)] -> TMap k aSource
Build a map from an ascending list in linear time. The precondition (input list is ascending) is not checked.
fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
fromAscListWith :: TKey k => (a -> a -> a) -> [(k, a)] -> TMap k aSource
Build a map from an ascending list in linear time with a combining function for equal keys. The precondition (input list is ascending) is not checked.
fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
fromAscListWithKey :: TKey k => (k -> a -> a -> a) -> [(k, a)] -> TMap k aSource
Build a map from an ascending list in linear time. The precondition (input list is ascending) is not checked.
fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
fromDistinctAscList :: TKey k => [(k, a)] -> TMap k aSource
Build a map from an ascending list of distinct elements in linear time. The precondition is not checked.
fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
Ordered vectors
fromAscVector :: (TKey k, Vector v (k, a)) => v (k, a) -> TMap k aSource
Equivalent to
.
fromAscList
(toList
xs)
fromAscVectorWith :: (TKey k, Vector v (k, a)) => (a -> a -> a) -> v (k, a) -> TMap k aSource
Equivalent to
.
fromAscListWith
f (toList
xs)
fromAscVectorWithKey :: (TKey k, Vector v (k, a)) => (k -> a -> a -> a) -> v (k, a) -> TMap k aSource
Equivalent to
.
fromAscListWithKey
f (toList
xs)
fromDistinctAscVector :: (TKey k, Vector v (k, a)) => v (k, a) -> TMap k aSource
Equivalent to
.
fromDistinctAscList
(toList
xs)
Filter
filter :: TKey k => (a -> Bool) -> TMap k a -> TMap k aSource
Filter all values that satisfy the predicate.
filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty
filterWithKey :: TKey k => (k -> a -> Bool) -> TMap k a -> TMap k aSource
Filter all keys/values that satisfy the predicate.
filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
partition :: TKey k => (a -> Bool) -> TMap k a -> (TMap k a, TMap k a)Source
Partition the map according to a predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also split
.
partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a") partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty) partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
partitionWithKey :: TKey k => (k -> a -> Bool) -> TMap k a -> (TMap k a, TMap k a)Source
Partition the map according to a predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also split
.
partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a") partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty) partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
mapMaybe :: TKey k => (a -> Maybe b) -> TMap k a -> TMap k bSource
O(n). Map values and collect the Just
results.
let f x = if x == "a" then Just "new a" else Nothing mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
mapMaybeWithKey :: TKey k => (k -> a -> Maybe b) -> TMap k a -> TMap k bSource
Map keys/values and collect the Just
results.
let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
mapEither :: TKey k => (a -> Either b c) -> TMap k a -> (TMap k b, TMap k c)Source
Map values and separate the Left
and Right
results.
let f a = if a < "c" then Left a else Right a mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")]) mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
mapEitherWithKey :: TKey k => (k -> a -> Either b c) -> TMap k a -> (TMap k b, TMap k c)Source
Map keys/values and separate the Left
and Right
results.
let f k a = if k < 5 then Left (k * 2) else Right (a ++ a) mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")]) mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
split :: TKey k => k -> TMap k a -> (TMap k a, TMap k a)Source
The expression (
) is a pair split
k map(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)
splitLookup :: TKey k => k -> TMap k a -> (TMap k a, Maybe a, TMap k a)Source
The expression (
) splits a map just
like splitLookup
k mapsplit
but also returns
.
lookup
k map
splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")]) splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a") splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a") splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty) splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)
Submap
isSubmapOf :: (TKey k, Eq a) => TMap k a -> TMap k a -> BoolSource
This function is defined as (
).
isSubmapOf
= isSubmapOfBy
(==)
isSubmapOfBy :: TKey k => (a -> b -> Bool) -> TMap k a -> TMap k b -> BoolSource
The expression (
) returns isSubmapOfBy
f t1 t2True
if
all keys in t1
are in tree t2
, and when f
returns True
when
applied to their respective values. For example, the following
expressions are all True
:
isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
But the following are all False
:
isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
Indexed
lookupIndex :: TKey k => k -> TMap k a -> Maybe IntSource
Lookup the index of a key. The index is a number from
0 up to, but not including, the size
of the map.
lookupIndex 2 (fromList [(5,"a"), (3,"b")]) == Nothing lookupIndex 3 (fromList [(5,"a"), (3,"b")]) == Just 0 lookupIndex 5 (fromList [(5,"a"), (3,"b")]) == Just 1 lookupIndex 6 (fromList [(5,"a"), (3,"b")]) == Nothing
findIndex :: TKey k => k -> TMap k a -> IntSource
Return the index of a key. The index is a number from
0 up to, but not including, the size
of the map. Calls error
when
the key is not a member
of the map.
findIndex 2 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0 findIndex 5 (fromList [(5,"a"), (3,"b")]) == 1 findIndex 6 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map
elemAt :: TKey k => Int -> TMap k a -> (k, a)Source
Retrieve an element by index. Calls error
when an
invalid index is used.
elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b") elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a") elemAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range
updateAt :: TKey k => (k -> a -> Maybe a) -> Int -> TMap k a -> TMap k aSource
Update the element at index. Calls error
when an
invalid index is used.
updateAt (\ _ _ -> Just "x") 0 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")] updateAt (\ _ _ -> Just "x") 1 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "x")] updateAt (\ _ _ -> Just "x") 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\ _ _ -> Just "x") (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\_ _ -> Nothing) 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" updateAt (\_ _ -> Nothing) 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" updateAt (\_ _ -> Nothing) 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\_ _ -> Nothing) (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range
deleteAt :: TKey k => Int -> TMap k a -> TMap k aSource
Delete the element at index.
Defined as (
).
deleteAt
i map = updateAt
(k x -> Nothing
) i map
deleteAt 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" deleteAt 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" deleteAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range deleteAt (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range
Min/Max
findMin :: TKey k => TMap k a -> (k, a)Source
The minimal key of the map. Calls error
if the map is empty.
findMin (fromList [(5,"a"), (3,"b")]) == (3,"b") findMin empty Error: empty map has no minimal element
findMax :: TKey k => TMap k a -> (k, a)Source
The maximal key of the map. Calls error
if the map is empty.
findMax (fromList [(5,"a"), (3,"b")]) == (5,"a") findMax empty Error: empty map has no maximal element
deleteMin :: TKey k => TMap k a -> TMap k aSource
Delete the minimal key. Returns an empty map if the map is empty.
deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")] deleteMin empty == empty
deleteMax :: TKey k => TMap k a -> TMap k aSource
Delete the maximal key. Returns an empty map if the map is empty.
deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")] deleteMax empty == empty
deleteFindMin :: TKey k => TMap k a -> ((k, a), TMap k a)Source
Delete and find the minimal element.
deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) deleteFindMin Error: can not return the minimal element of an empty map
deleteFindMax :: TKey k => TMap k a -> ((k, a), TMap k a)Source
Delete and find the maximal element.
deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList[(3,"b"),(5,"a")]) deleteFindMax Error: can not return the maximal element of an empty map
updateMin :: TKey k => (a -> Maybe a) -> TMap k a -> TMap k aSource
Update the value at the minimal key.
updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")] updateMin (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
updateMax :: TKey k => (a -> Maybe a) -> TMap k a -> TMap k aSource
Update the value at the maximal key.
updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")] updateMax (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
updateMinWithKey :: TKey k => (k -> a -> Maybe a) -> TMap k a -> TMap k aSource
Update the value at the minimal key.
updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")] updateMinWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
updateMaxWithKey :: TKey k => (k -> a -> Maybe a) -> TMap k a -> TMap k aSource
Update the value at the maximal key.
updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")] updateMaxWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
minView :: TKey k => TMap k a -> Maybe (a, TMap k a)Source
Retrieves the value associated with minimal key of the
map, and the map stripped of that element, or Nothing
if passed an
empty map.
minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a") minView empty == Nothing
maxView :: TKey k => TMap k a -> Maybe (a, TMap k a)Source
Retrieves the value associated with maximal key of the
map, and the map stripped of that element, or Nothing
if passed an
maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b") maxView empty == Nothing
minViewWithKey :: TKey k => TMap k a -> Maybe ((k, a), TMap k a)Source
Retrieves the minimal (key,value) pair of the map, and
the map stripped of that element, or Nothing
if passed an empty map.
minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a") minViewWithKey empty == Nothing
maxViewWithKey :: TKey k => TMap k a -> Maybe ((k, a), TMap k a)Source
O(log n). Retrieves the maximal (key,value) pair of the map, and
the map stripped of that element, or Nothing
if passed an empty map.
maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b") maxViewWithKey empty == Nothing