We will use the following terminology:
An algebraic type is a type isomorphic to an algebraic type, as defined in the package description. This isomorphism is
declared via the type class Algebraic
, where
is algebraic. It is assumed for purposes of ordering that
this isomorphism is order- and equality-preserving. We also require that if Alg
kk
is algebraic,
.
Alg
k ~ k
These methods will automatically infer the correct type of a TrieMap
on any given argument. For example,
fromList
[(("alphabet",Just
(0.2 ::Double
),True
), "wxyz")]
returns a variable of type
TrieMap
(String
,Double
,Bool
) (RadixTrie
Int
IntMap
`ProdMap
`UnionMap
Maybe
(Map
Double
) `ProdMap
`UnionMap
Maybe
Maybe
)String
The inference was done entirely automatically. Note also:
-
: theAlg
Char
~Int
Algebraic
instance forChar
maps characters to their ASCII representations, so anIntMap
can be used. -
; aAlg
(Maybe
a) ~Either
() (Alg
a)TrieMap
on aMaybe
key type simply gets a space for one extra (possible) value. -
; theAlg
Double
~Ordered
Double
Algebraic
instance forDouble
tells TrieMap to just use a regularMap
and the default ordering forDouble
s. -
, so aAlg
Bool
~Either
() ()TrieMap
on aBool
takes the form of -- essentially -- a pair ofMaybe
s. -
, so tuple types get handled by a sequence of map products.Alg
(a, b, c) ~ (Alg
a, (Alg
b,Alg
c))
(If you plan to use these maps in type arguments, it is strongly suggested that you either reproduce the context
(
, or you create a type alias!)
Algebraic
k, TrieKey
(Alg
k) m) => TrieMap k m a
- data TrieMap k m a
- class (Eq a, Foldable m, Traversable m) => TrieKey a m | a -> m, m -> a
- class Algebraic k where
- data ProdMap m1 m2 v
- data UnionMap m1 m2 v
- data RadixTrie k m v
- (!) :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> k -> a
- (\\) :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m a
- null :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Bool
- size :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Int
- member :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> Bool
- notMember :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> Bool
- lookup :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> Maybe a
- find :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> a
- findWithDefault :: (Algebraic k, TrieKey (Alg k) m) => a -> k -> TrieMap k m a -> a
- empty :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a
- singleton :: (Algebraic k, TrieKey (Alg k) m) => k -> a -> TrieMap k m a
- insert :: (Algebraic k, TrieKey (Alg k) m) => k -> a -> TrieMap k m a -> TrieMap k m a
- insertWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> k -> a -> TrieMap k m a -> TrieMap k m a
- insertWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> k -> a -> TrieMap k m a -> TrieMap k m a
- insertLookupWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> k -> a -> TrieMap k m a -> (Maybe a, TrieMap k m a)
- delete :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> TrieMap k m a
- update :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m a
- updateWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m a
- updateLookupWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> k -> TrieMap k m a -> (Maybe a, TrieMap k m a)
- alter :: (Algebraic k, TrieKey (Alg k) m) => (Maybe a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m a
- alterLookup :: (Algebraic k, TrieKey (Alg k) m) => (Maybe a -> Maybe a) -> k -> TrieMap k m a -> (Maybe a, TrieMap k m a)
- union :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m a -> TrieMap k m a
- unionWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a
- unionWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a
- unions :: (Algebraic k, TrieKey (Alg k) m) => [TrieMap k m a] -> TrieMap k m a
- unionsWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [TrieMap k m a] -> TrieMap k m a
- unionsWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [TrieMap k m a] -> TrieMap k m a
- unionMaybeWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a
- unionMaybeWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a
- symDifference :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m a -> TrieMap k m a
- intersection :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m a
- intersectionWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m c
- intersectionWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m c
- intersectionMaybeWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Maybe c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m c
- intersectionMaybeWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> Maybe c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m c
- difference :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m a
- differenceWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Maybe a) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m a
- differenceWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> Maybe a) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m a
- map :: (Algebraic k, TrieKey (Alg k) m) => (a -> b) -> TrieMap k m a -> TrieMap k m b
- mapWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b) -> TrieMap k m a -> TrieMap k m b
- mapApp :: (Algebraic k, TrieKey (Alg k) m, Applicative f) => (a -> f b) -> TrieMap k m a -> f (TrieMap k m b)
- mapAppWithKey :: (Algebraic k, TrieKey (Alg k) m, Applicative f) => (k -> a -> f b) -> TrieMap k m a -> f (TrieMap k m b)
- mapMaybe :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe b) -> TrieMap k m a -> TrieMap k m b
- mapMaybeWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe b) -> TrieMap k m a -> TrieMap k m b
- mapEither :: (Algebraic k, TrieKey (Alg k) m) => (a -> Either b c) -> TrieMap k m a -> (TrieMap k m b, TrieMap k m c)
- mapEitherWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Either b c) -> TrieMap k m a -> (TrieMap k m b, TrieMap k m c)
- mapKeys :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 a
- mapKeysWith :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (a -> a -> a) -> (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 a
- mapKeysMonotonic :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 a
- fold :: TrieKey k m => (a -> b -> b) -> b -> TrieMap k m a -> b
- foldWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> b) -> b -> TrieMap k m a -> b
- elems :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> [a]
- keys :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> [k]
- assocs :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> [(k, a)]
- fromList :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m a
- fromListWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [(k, a)] -> TrieMap k m a
- fromListWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [(k, a)] -> TrieMap k m a
- fromAscList :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m a
- fromAscListWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [(k, a)] -> TrieMap k m a
- fromAscListWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [(k, a)] -> TrieMap k m a
- fromDistinctAscList :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m a
- filter :: (Algebraic k, TrieKey (Alg k) m) => (a -> Bool) -> TrieMap k m a -> TrieMap k m a
- filterWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Bool) -> TrieMap k m a -> TrieMap k m a
- partition :: (Algebraic k, TrieKey (Alg k) m) => (a -> Bool) -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a)
- partitionWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Bool) -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a)
- split :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a)
- splitLookup :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> (TrieMap k m a, Maybe a, TrieMap k m a)
- isSubmapOf :: (Algebraic k, TrieKey (Alg k) m, Eq a) => TrieMap k m a -> TrieMap k m a -> Bool
- isSubmapOfBy :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Bool) -> TrieMap k m a -> TrieMap k m b -> Bool
- findMin :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> (k, a)
- getMin :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (k, a)
- findMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> (k, a)
- getMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (k, a)
- deleteMin :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m a
- deleteMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m a
- deleteFindMin :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> ((k, a), TrieMap k m a)
- deleteFindMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> ((k, a), TrieMap k m a)
- updateMin :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> TrieMap k m a -> TrieMap k m a
- updateMax :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> TrieMap k m a -> TrieMap k m a
- updateMinWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a
- updateMaxWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a
- minView :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (a, TrieMap k m a)
- maxView :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (a, TrieMap k m a)
- minViewWithKey :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe ((k, a), TrieMap k m a)
- maxViewWithKey :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe ((k, a), TrieMap k m a)
Map type
A TrieMap
is a size-tracking wrapper around a generalized trie map.
Functor m => Functor (TrieMap k m) | |
Foldable m => Foldable (TrieMap k m) | |
Traversable m => Traversable (TrieMap k m) | |
(Eq k, Eq a, Algebraic k, TrieKey (Alg k) m) => Eq (TrieMap k m a) | |
(Ord k, Ord a, Algebraic k, TrieKey (Alg k) m) => Ord (TrieMap k m a) | |
(Show k, Show a, Algebraic k, TrieKey (Alg k) m) => Show (TrieMap k m a) | |
(Algebraic k, TrieKey (Alg k) m) => Monoid (TrieMap k m a) | |
(Algebraic k, Algebraic a, TrieKey (Alg k) m) => Algebraic (TrieMap k m a) |
class (Eq a, Foldable m, Traversable m) => TrieKey a m | a -> m, m -> aSource
TrieKey defines a bijection between map types and algebraic key types.
Algebraic
refers to a type with an algebraic representation, armed with methods to convert in each direction.
toAlg
and fromAlg
should preserve equality and ordering.
Algebraic Bool | |
Algebraic Char | |
Algebraic Double | |
Algebraic Float | |
Algebraic Int | |
Algebraic Rational | |
Algebraic () | |
Algebraic IntSet | |
Algebraic k => Algebraic [k] | |
Algebraic a => Algebraic (Maybe a) | |
Algebraic v => Algebraic (IntMap v) | |
Algebraic a => Algebraic (Set a) | |
(Algebraic k1, Algebraic k2) => Algebraic (Either k1 k2) | |
(Algebraic k1, Algebraic k2) => Algebraic (k1, k2) | |
(Algebraic k, Algebraic v) => Algebraic (Map k v) | |
(Algebraic a, Algebraic b, Algebraic c) => Algebraic (a, b, c) | |
(Ord k, Algebraic k, Algebraic v, TrieKey k m) => Algebraic (RadixTrie k m v) | |
(Algebraic (m1 v), Algebraic (m2 v)) => Algebraic (UnionMap m1 m2 v) | |
Algebraic (m1 (m2 v)) => Algebraic (ProdMap m1 m2 v) | |
(Algebraic k, Algebraic a, TrieKey (Alg k) m) => Algebraic (TrieMap k m a) | |
(Algebraic a, Algebraic b, Algebraic c, Algebraic d) => Algebraic (a, b, c, d) | |
(Algebraic a, Algebraic b, Algebraic c, Algebraic d, Algebraic e) => Algebraic (a, b, c, d, e) |
Map instances
ProdMap
is used to hold a map on the product of two key types.
(Functor m1, Functor m2) => Functor (ProdMap m1 m2) | |
(Foldable m1, Foldable m2) => Foldable (ProdMap m1 m2) | |
(Traversable m1, Traversable m2) => Traversable (ProdMap m1 m2) | |
(Eq a1, Eq a2, TrieKey a1 m1, TrieKey a2 m2) => TrieKey (a1, a2) (ProdMap m1 m2) | |
Eq (m1 (m2 v)) => Eq (ProdMap m1 m2 v) | |
Ord (m1 (m2 v)) => Ord (ProdMap m1 m2 v) | |
Algebraic (m1 (m2 v)) => Algebraic (ProdMap m1 m2 v) |
UnionMap
is used to hold a map on the sum of two key types.
(Functor m1, Functor m2) => Functor (UnionMap m1 m2) | |
(Foldable m1, Foldable m2) => Foldable (UnionMap m1 m2) | |
(Traversable m1, Traversable m2) => Traversable (UnionMap m1 m2) | |
(TrieKey a1 m1, TrieKey a2 m2) => TrieKey (Either a1 a2) (UnionMap m1 m2) | |
(Eq (m1 v), Eq (m2 v)) => Eq (UnionMap m1 m2 v) | |
(Ord (m1 v), Ord (m2 v)) => Ord (UnionMap m1 m2 v) | |
(Algebraic (m1 v), Algebraic (m2 v)) => Algebraic (UnionMap m1 m2 v) |
RadixTrie
is used to hold a map on a list of keys.
(Ord k, TrieKey k m) => TrieKey [k] (RadixTrie k m) | |
Functor m => Functor (RadixTrie k m) | |
Foldable m => Foldable (RadixTrie k m) | |
Traversable m => Traversable (RadixTrie k m) | |
(Eq k, Eq v, TrieKey k m) => Eq (RadixTrie k m v) | |
(Ord k, Ord v, TrieKey k m) => Ord (RadixTrie k m v) | |
(Show k, Show v, Functor m, Show (m String)) => Show (RadixTrie k m v) | |
(Ord k, Algebraic k, Algebraic v, TrieKey k m) => Algebraic (RadixTrie k m v) |
Operators
(!) :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> k -> aSource
Find the value at a key.
Calls error
when the element can not be found.
fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map fromList [(5,'a'), (3,'b')] ! 5 == 'a'
(\\) :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource
Same as difference
.
Query
null :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> BoolSource
Check if the specified map is empty.
size :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> IntSource
Returns the size of the specified map.
member :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m 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
find :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> aSource
Find the value at a key.
Calls error
when the element can not be found.
findWithDefault :: (Algebraic k, TrieKey (Alg k) m) => a -> k -> TrieMap k m 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.
findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x' findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
Construction
singleton :: (Algebraic k, TrieKey (Alg k) m) => k -> a -> TrieMap k m aSource
O(1). A map with a single element.
singleton 1 'a' == fromList [(1, 'a')]
Insertion
insert :: (Algebraic k, TrieKey (Alg k) m) => k -> a -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> k -> a -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> k -> a -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> k -> a -> TrieMap k m a -> (Maybe a, TrieMap k m 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
Delete/Update
delete :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> TrieMap k m 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
update :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m 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"
updateLookupWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> k -> TrieMap k m a -> (Maybe a, TrieMap k m a)Source
Lookup and update. See also updateWithKey
.
The function returns changed value, if it is updated.
Returns the original key value if the map entry is deleted.
let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "5:new a", fromList [(3, "b"), (5, "5:new a")]) updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a")]) updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
alter :: (Algebraic k, TrieKey (Alg k) m) => (Maybe a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m aSource
The expression (
) alters the value alter
f k mapx
at k
, or absence thereof.
alter
can be used to insert, delete, or update a value in a Map
.
In short :
.
lookup
k (alter
f k m) = f (lookup
k m)
let f _ = Nothing alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" let f _ = Just "c" alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")] alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]
alterLookup :: (Algebraic k, TrieKey (Alg k) m) => (Maybe a -> Maybe a) -> k -> TrieMap k m a -> (Maybe a, TrieMap k m a)Source
The expression (
) alters the value alterLookup
f k mapx
at k
, or absence thereof, and returns the old value.
alterLookup
can be used to insert, delete, or update a value in a Map
.
In short : alterLookup f k m = (lookup k m, alter f k m)
.
Combine
Union/Symmetric Difference
unionWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource
O(n+m). Union with a combining function.
unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
unionWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource
O(n+m). Union with a combining function.
let f key left_value right_value = (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")]
unionsWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [TrieMap k m a] -> TrieMap k m aSource
unionsWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [TrieMap k m a] -> TrieMap k m aSource
unionMaybeWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource
O(n+m). Union with a combining function that may discard some elements.
unionMaybeWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource
O(n+m). Union with a combining function that may discard some elements.
symDifference :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource
O(n+m). Symmetric difference. Equivalent to
.
unionMaybeWith
( _ _ -> Nothing)
Intersection
intersection :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource
O(n+m). 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m cSource
O(n+m). Intersection with a combining function.
intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
intersectionWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m cSource
O(n+m). Intersection with a combining function.
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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Maybe c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m cSource
O(n+m). Intersection of two maps with a combining function that may discard some elements.
intersectionMaybeWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> Maybe c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m cSource
O(n+m). Intersection of two maps with a combining function that may discard some elements.
Difference
difference :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource
O(n+m). 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"
differenceWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Maybe a) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource
O(n+m). 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
.
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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> Maybe a) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource
O(n+m). 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
.
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"
Traversal
Map
map :: (Algebraic k, TrieKey (Alg k) m) => (a -> b) -> TrieMap k m a -> TrieMap k m bSource
O(n). Map a function over all values in the map.
map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
mapWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b) -> TrieMap k m a -> TrieMap k m bSource
O(n). 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")]
mapApp :: (Algebraic k, TrieKey (Alg k) m, Applicative f) => (a -> f b) -> TrieMap k m a -> f (TrieMap k m b)Source
Equivalent to traverse
.
mapAppWithKey :: (Algebraic k, TrieKey (Alg k) m, Applicative f) => (k -> a -> f b) -> TrieMap k m a -> f (TrieMap k m b)Source
Essentially equivalent to traverse
with a function that takes both the key and the value as arguments.
mapMaybe :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe b) -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe b) -> TrieMap k m a -> TrieMap k m bSource
O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Either b c) -> TrieMap k m a -> (TrieMap k m b, TrieMap k m c)Source
O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Either b c) -> TrieMap k m a -> (TrieMap k m b, TrieMap k m c)Source
O(n). 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")])
mapKeys :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 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 :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (a -> a -> a) -> (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 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 :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 aSource
O(n).
, 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")] valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True valid (mapKeysMonotonic (\ _ -> 1) (fromList [(5,"a"), (3,"b")])) == False
Fold
foldWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> b) -> b -> TrieMap k m a -> bSource
O(n). Fold the keys and values in the map, such that
.
For example,
foldWithKey
f z == foldr
(uncurry
f) z . assocs
keys map = foldWithKey (\k x ks -> k:ks) [] map
let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")" foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
Conversion
elems :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> [a]Source
O(n). Return all elements of the map in the ascending order of their keys.
elems (fromList [(5,"a"), (3,"b")]) == ["b","a"] elems empty == []
keys :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> [k]Source
O(n). Return all keys of the map in ascending order.
keys (fromList [(5,"a"), (3,"b")]) == [3,5] keys empty == []
assocs :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> [(k, a)]Source
O(n). Return all key/value pairs in the map in ascending key order.
assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")] assocs empty == []
Lists
fromList :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [(k, a)] -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [(k, a)] -> TrieMap k m aSource
Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey
.
let f k a1 a2 = (show k) ++ a1 ++ a2 fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")] fromListWithKey f [] == empty
Ordered lists
fromAscList :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m aSource
O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [(k, a)] -> TrieMap k m aSource
O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [(k, a)] -> TrieMap k m aSource
O(n). 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.
let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2 fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
fromDistinctAscList :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m aSource
O(n). 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")]
Filter
filter :: (Algebraic k, TrieKey (Alg k) m) => (a -> Bool) -> TrieMap k m a -> TrieMap k m aSource
O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Bool) -> TrieMap k m a -> TrieMap k m aSource
O(n). Filter all keys/values that satisfy the predicate.
filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
partition :: (Algebraic k, TrieKey (Alg k) m) => (a -> Bool) -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a)Source
O(n). 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.
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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Bool) -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a)Source
O(n). 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.
partitionWithKey (\ k _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b") partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty) partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
split :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> (TrieMap k m a, TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> (TrieMap k m a, Maybe a, TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m, Eq a) => TrieMap k m a -> TrieMap k m a -> BoolSource
O(n+m).
This function is defined as (
).
isSubmapOf
= isSubmapOfBy
(==)
isSubmapOfBy :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Bool) -> TrieMap k m a -> TrieMap k m b -> BoolSource
O(n+m).
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)])
Min/Max
findMin :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m 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
getMin :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (k, a)Source
The minimal key of the map, if any. Returns Nothing
if the map is empty.
getMin (fromList [(5,"a"), (3,"b")]) == Just (3,"b") getMin empty == Nothing
findMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> (k, a)Source
The maximal key of the map. Calls error
is the map is empty.
findMax (fromList [(5,"a"), (3,"b")]) == (5,"a") findMax empty Error: empty map has no maximal element
getMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (k, a)Source
The maximal key of the map, if any. Returns Nothing
if the map is empty.
getMax (fromList [(5,"a"), (3,"b")]) == Just (5,"a") getMax empty == Nothing
deleteMin :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> ((k, a), TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> ((k, a), TrieMap k m a)Source
Delete and find the maximal element.
deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")]) deleteFindMax empty Error: can not return the maximal element of an empty map
updateMin :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (a, TrieMap k m a)Source
Retrieves the value associated with the 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (a, TrieMap k m a)Source
Retrieves the value associated with the 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe ((k, a), TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe ((k, a), TrieMap k m a)Source
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