The base implementation of a trie representing a map with list keys, generalized over any type of map from element values to tries.
Worst-case complexities are given in terms of n
, m
, and k
. n
refers
to the number of keys in the map and m
to their maximum length. k
refers
to the length of a key given to the function, not any property of the map.
In addition, the trie's branching factor plays a part in almost every
operation, but the complexity depends on the underlying Map
. Thus, for
instance, member
is actually O(m f(b))
where f(b)
is the complexity of
a lookup operation on the Map
used. This complexity depends on the
underlying operation, which is not part of the specification of the visible
function. Thus it could change whilst affecting the complexity only for
certain Map types: hence this "b factor" is not shown explicitly.
Disclaimer: the complexities have not been proven.
Strict versions of functions are provided for those who want to be certain
that their TrieMap
doesn't contain values consisting of unevaluated
thunks. Note, however, that they do not evaluate the whole trie strictly,
only the values. And only to one level of depth: for instance, alter'
does
not seq
the value within the Maybe
, only the Maybe
itself. The user
should add the strictness in such cases himself, if he so wishes.
Many functions come in both ordinary and WithKey
forms, where the former
takes a function of type a -> b
and the latter of type [k] -> a -> b
,
where [k]
is the key associated with the value a
. For most of these
functions, there is additional overhead involved in keeping track of the
key: don't use the latter form of the function unless you need it.
- data TrieMap map k v
- empty :: Map map k => TrieMap map k a
- singleton :: Map map k => [k] -> a -> TrieMap map k a
- insert :: Map map k => [k] -> a -> TrieMap map k a -> TrieMap map k a
- insert' :: Map map k => [k] -> a -> TrieMap map k a -> TrieMap map k a
- insertWith :: Map map k => (a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k a
- insertWith' :: Map map k => (a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k a
- delete :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a
- update :: Map map k => (a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
- updateLookup :: Map map k => (a -> Maybe a) -> [k] -> TrieMap map k a -> (Maybe a, TrieMap map k a)
- adjust :: Map map k => (a -> a) -> [k] -> TrieMap map k a -> TrieMap map k a
- adjust' :: Map map k => (a -> a) -> [k] -> TrieMap map k a -> TrieMap map k a
- alter :: Map map k => (Maybe a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
- alter' :: Map map k => (Maybe a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
- null :: Map map k => TrieMap map k a -> Bool
- size :: (Map map k, Num n) => TrieMap map k a -> n
- size' :: (Map map k, Num n) => TrieMap map k a -> n
- member :: Map map k => [k] -> TrieMap map k a -> Bool
- notMember :: Map map k => [k] -> TrieMap map k a -> Bool
- lookup :: Map map k => [k] -> TrieMap map k a -> Maybe a
- lookupWithDefault :: Map map k => a -> [k] -> TrieMap map k a -> a
- isSubmapOf :: (Map map k, Eq a) => TrieMap map k a -> TrieMap map k a -> Bool
- isSubmapOfBy :: Map map k => (a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
- isProperSubmapOf :: (Map map k, Eq a) => TrieMap map k a -> TrieMap map k a -> Bool
- isProperSubmapOfBy :: Map map k => (a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
- union :: Map map k => TrieMap map k a -> TrieMap map k a -> TrieMap map k a
- union' :: Map map k => TrieMap map k a -> TrieMap map k a -> TrieMap map k a
- unions :: Map map k => [TrieMap map k a] -> TrieMap map k a
- unions' :: Map map k => [TrieMap map k a] -> TrieMap map k a
- unionWith :: Map map k => (a -> a -> a) -> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
- unionWithKey :: Map map k => ([k] -> a -> a -> a) -> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
- unionsWith :: Map map k => (a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
- unionsWithKey :: Map map k => ([k] -> a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
- unionWith' :: Map map k => (a -> a -> a) -> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
- unionWithKey' :: Map map k => ([k] -> a -> a -> a) -> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
- unionsWith' :: Map map k => (a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
- unionsWithKey' :: Map map k => ([k] -> a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
- difference :: Map map k => TrieMap map k a -> TrieMap map k b -> TrieMap map k a
- differenceWith :: Map map k => (a -> b -> Maybe a) -> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
- differenceWithKey :: Map map k => ([k] -> a -> b -> Maybe a) -> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
- intersection :: Map map k => TrieMap map k a -> TrieMap map k b -> TrieMap map k a
- intersection' :: Map map k => TrieMap map k a -> TrieMap map k b -> TrieMap map k a
- intersectionWith :: Map map k => (a -> b -> c) -> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
- intersectionWithKey :: Map map k => ([k] -> a -> b -> c) -> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
- intersectionWith' :: Map map k => (a -> b -> c) -> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
- intersectionWithKey' :: Map map k => ([k] -> a -> b -> c) -> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
- filter :: Map map k => (a -> Bool) -> TrieMap map k a -> TrieMap map k a
- filterWithKey :: Map map k => ([k] -> a -> Bool) -> TrieMap map k a -> TrieMap map k a
- partition :: Map map k => (a -> Bool) -> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
- partitionWithKey :: Map map k => ([k] -> a -> Bool) -> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
- mapMaybe :: Map map k => (a -> Maybe b) -> TrieMap map k a -> TrieMap map k b
- mapMaybeWithKey :: Map map k => ([k] -> a -> Maybe b) -> TrieMap map k a -> TrieMap map k b
- mapEither :: Map map k => (a -> Either b c) -> TrieMap map k a -> (TrieMap map k b, TrieMap map k c)
- mapEitherWithKey :: Map map k => ([k] -> a -> Either b c) -> TrieMap map k a -> (TrieMap map k b, TrieMap map k c)
- map :: Map map k => (a -> b) -> TrieMap map k a -> TrieMap map k b
- map' :: Map map k => (a -> b) -> TrieMap map k a -> TrieMap map k b
- mapWithKey :: Map map k => ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
- mapWithKey' :: Map map k => ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
- mapKeys :: (Map map k1, Map map k2) => ([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a
- mapKeysWith :: (Map map k1, Map map k2) => (a -> a -> a) -> ([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a
- mapInKeys :: (Map map k1, Map map k2) => (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
- mapInKeys' :: (Map map k1, Map map k2) => (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
- mapInKeysWith :: (Map map k1, Map map k2) => (a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
- mapInKeysWith' :: (Map map k1, Map map k2) => (a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
- mapAccum :: Map map k => (acc -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumWithKey :: Map map k => (acc -> [k] -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccum' :: Map map k => (acc -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumWithKey' :: Map map k => (acc -> [k] -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumAsc :: OrdMap map k => (acc -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumAscWithKey :: OrdMap map k => (acc -> [k] -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumAsc' :: OrdMap map k => (acc -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumAscWithKey' :: OrdMap map k => (acc -> [k] -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumDesc :: OrdMap map k => (acc -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumDescWithKey :: OrdMap map k => (acc -> [k] -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumDesc' :: OrdMap map k => (acc -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- mapAccumDescWithKey' :: OrdMap map k => (acc -> [k] -> a -> (acc, b)) -> acc -> TrieMap map k a -> (acc, TrieMap map k b)
- foldr :: Map map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldrWithKey :: Map map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- foldrAsc :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldrAscWithKey :: OrdMap map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- foldrDesc :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldrDescWithKey :: OrdMap map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- foldl :: Map map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldlWithKey :: Map map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- foldlAsc :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldlAscWithKey :: OrdMap map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- foldlDesc :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldlDescWithKey :: OrdMap map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- foldl' :: Map map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldlWithKey' :: Map map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- foldlAsc' :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldlAscWithKey' :: OrdMap map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- foldlDesc' :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
- foldlDescWithKey' :: OrdMap map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
- toList :: Map map k => TrieMap map k a -> [([k], a)]
- toAscList :: OrdMap map k => TrieMap map k a -> [([k], a)]
- toDescList :: OrdMap map k => TrieMap map k a -> [([k], a)]
- fromList :: Map map k => [([k], a)] -> TrieMap map k a
- fromListWith :: Map map k => (a -> a -> a) -> [([k], a)] -> TrieMap map k a
- fromListWithKey :: Map map k => ([k] -> a -> a -> a) -> [([k], a)] -> TrieMap map k a
- fromListWith' :: Map map k => (a -> a -> a) -> [([k], a)] -> TrieMap map k a
- fromListWithKey' :: Map map k => ([k] -> a -> a -> a) -> [([k], a)] -> TrieMap map k a
- minView :: OrdMap map k => TrieMap map k a -> (Maybe ([k], a), TrieMap map k a)
- maxView :: OrdMap map k => TrieMap map k a -> (Maybe ([k], a), TrieMap map k a)
- findMin :: OrdMap map k => TrieMap map k a -> Maybe ([k], a)
- findMax :: OrdMap map k => TrieMap map k a -> Maybe ([k], a)
- deleteMin :: OrdMap map k => TrieMap map k a -> TrieMap map k a
- deleteMax :: OrdMap map k => TrieMap map k a -> TrieMap map k a
- split :: OrdMap map k => [k] -> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
- splitLookup :: OrdMap map k => [k] -> TrieMap map k a -> (TrieMap map k a, Maybe a, TrieMap map k a)
- findPredecessor :: OrdMap map k => [k] -> TrieMap map k a -> Maybe ([k], a)
- findSuccessor :: OrdMap map k => [k] -> TrieMap map k a -> Maybe ([k], a)
- addPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a
- deletePrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a
- splitPrefix :: Map map k => TrieMap map k a -> ([k], Maybe a, TrieMap map k a)
- children :: Map map k => TrieMap map k a -> [(k, TrieMap map k a)]
- showTrie :: (Show k, Show a, Map map k) => TrieMap map k a -> ShowS
- showTrieWith :: (Show k, Map map k) => (Maybe a -> ShowS) -> TrieMap map k a -> ShowS
Map type
The data structure itself: a map from keys of type [k]
to values of type
v
implemented as a trie, using map
to map keys of type k
to sub-tries.
Regarding the instances:
- The
Trie
class is internal, ignore it. - The
Eq
constraint for theOrd
instance is misleading: it is needed only becauseEq
is a superclass ofOrd
. - The
Foldable
andTraversable
instances allow folding over and traversing only the values, not the keys. - The
Monoid
instance definesmappend
asunion
andmempty
asempty
.
Map map k => Trie TrieMap Maybe map k | |
Map map k => Functor (TrieMap map k) | |
Map map k => Foldable (TrieMap map k) | |
(Map map k, Traversable (map k)) => Traversable (TrieMap map k) | |
(Eq (map k (TrieMap map k a)), Eq a) => Eq (TrieMap map k a) | |
(Eq (map k (TrieMap map k a)), OrdMap map k, Ord k, Ord a) => Ord (TrieMap map k a) | |
(Map map k, Read k, Read a) => Read (TrieMap map k a) | |
(Map map k, Show k, Show a) => Show (TrieMap map k a) | |
Map map k => Monoid (TrieMap map k a) |
Construction
singleton :: Map map k => [k] -> a -> TrieMap map k aSource
O(s)
. The singleton map containing only the given key-value pair.
Modification
insert :: Map map k => [k] -> a -> TrieMap map k a -> TrieMap map k aSource
O(min(m,s))
. Inserts the key-value pair into the map. If the key is
already a member of the map, the given value replaces the old one.
insert' :: Map map k => [k] -> a -> TrieMap map k a -> TrieMap map k aSource
O(min(m,s))
. Inserts the key-value pair into the map. If the key is
already a member of the map, the given value replaces the old one.
insertWith :: Map map k => (a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k aSource
O(min(m,s))
. Inserts the key-value pair into the map. If the key is
already a member of the map, the old value is replaced by f givenValue
oldValue
where f
is the given function.
insertWith' :: Map map k => (a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k aSource
O(min(m,s))
. Like insertWith
, but the new value is reduced to weak
head normal form before being placed into the map, whether it is the given
value or a result of the combining function.