TrieMap

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 Alg k is algebraic. It is assumed for purposes of ordering that this isomorphism is order- and equality-preserving. We also require that if k 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:

• Alg Char ~ Int: the Algebraic instance for Char maps characters to their ASCII representations, so an IntMap can be used.
• Alg (Maybe a) ~ Either () (Alg a); a TrieMap on a Maybe key type simply gets a space for one extra (possible) value.
• Alg Double ~ Ordered Double; the Algebraic instance for Double tells TrieMap to just use a regular Map and the default ordering for Doubles.
• Alg Bool ~ Either () (), so a TrieMap on a Bool takes the form of -- essentially -- a pair of Maybes.
• Alg (a, b, c) ~ (Alg a, (Alg b, Alg c)), so tuple types get handled by a sequence of map products.

(If you plan to use these maps in type arguments, it is strongly suggested that you either reproduce the context (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a, or you create a type alias!)

Map type

data TrieMap k m a

A TrieMap is a size-tracking wrapper around a generalized trie map.

Instances

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 -> a

TrieKey defines a bijection between map types and algebraic key types.

Instances

TrieKey Int IntMap

TrieKey () Maybe

Ord k => TrieKey (Ordered k) (Map k)

(Ord k, TrieKey k m) => TrieKey [k] (RadixTrie k m)

(TrieKey a1 m1, TrieKey a2 m2) => TrieKey (Either a1 a2) (UnionMap m1 m2)

(Eq a1, Eq a2, TrieKey a1 m1, TrieKey a2 m2) => TrieKey (a1, a2) (ProdMap m1 m2)

class Algebraic k where

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.

Associated Types

type Alg k

Alg k is a fully decomposed representation of k into algebraic pieces.

Methods

toAlg :: k -> Alg k

fromAlg :: Alg k -> k

Instances

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 v => Algebraic (Elem v)

(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, Sized v, 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

data ProdMap m1 m2 v

ProdMap is used to hold a map on the product of two key types.

Instances

(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)

data UnionMap m1 m2 v

UnionMap is used to hold a map on the sum of two key types.

Instances

(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)

data RadixTrie k m v

RadixTrie is used to hold a map on a list of keys.

Instances

(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, Sized v, Algebraic v, TrieKey k m) => Algebraic (RadixTrie k m v)

Operators

(!) :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> k -> a

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 a

Same as difference.

Query

null :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Bool

Check if the specified map is empty.

size :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Int

Returns the size of the specified map.

member :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> Bool

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 -> Bool

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

lookup :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> Maybe a

Lookup the value of a key in the map.

The function will return the corresponding value as (Just value), or Nothing if the key isn't in the map.

find :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> a

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 -> a

The expression (findWithDefault def k map) returns the value at key 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

empty :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a

singleton :: (Algebraic k, TrieKey (Alg k) m) => k -> a -> TrieMap k m a

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 a

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 a

Insert with a function, combining new value and old value. insertWith f key value mp will insert the pair (key, value) into mp 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 a

Insert with a function, combining key, new value and old value. insertWithKey f key value mp will insert the pair (key, value) into mp 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)

Combines insert operation with old value retrieval. The expression (insertLookupWithKey f k x map) is a pair where the first element is equal to (lookup k map) and the second element equal to (insertWithKey f k x map).

Delete/Update

delete :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> TrieMap k m a

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

delete is equivalent to alter (const Nothing).

update :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m a

The expression (update f k map) updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k 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 a

The expression (updateWithKey f k map) updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k 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)

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 a

The expression (alter f k map) alters the value x 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)

The expression (alterLookup f k map) alters the value x 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

union :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m a -> TrieMap k m a

O(n+m). The expression (union t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered, i.e. (union == unionWith const).

 union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]

unionWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a

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 a

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")]

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

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 a

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 a

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 a

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 c

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 c

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 c

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 c

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 a

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 a

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 (Just y), the element is updated with a new value y.

 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 a

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 (Just y), the element is updated with a new value y.

 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 b

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 b

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)

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)

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 b

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 b

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)

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)

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 a

mapKeys f s is the map obtained by applying f 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 a

mapKeysWith c f s is the map obtained by applying f 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 a

O(n). mapKeysMonotonic f s == mapKeys f s, but works only when f 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

fold :: TrieKey k m => (a -> b -> b) -> b -> TrieMap k m a -> b

O(n). Fold the values in the map, such that fold f z == foldr f z . elems. For example,

 elems map = fold (:) [] map

 let f a len = len + (length a)
 fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

foldWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> b) -> b -> TrieMap k m a -> b

O(n). Fold the keys and values in the map, such that foldWithKey f z == foldr (uncurry f) z . assocs. For example,

 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]

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]

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)]

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 a

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 a

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 a

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 a

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 a

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 a

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 a

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 a

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 a

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)

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)

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)

The expression (split k map) is a pair (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)

The expression (splitLookup k map) splits a map just like split 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 -> Bool

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 -> Bool

O(n+m). The expression (isSubmapOfBy f t1 t2) returns True 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)

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)

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)

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)

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 a

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 a

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)

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)

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 a

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 a

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 a

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 a

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)

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)

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)

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)

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