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 the Ord instance is misleading: it is needed only because Eq is a superclass of Ord.
• The Foldable and Traversable instances allow folding over and traversing only the values, not the keys.
• The Monoid instance defines mappend as union and mempty as empty.

O(1). The empty map.

O(1). The singleton map containing only the given key-value pair.

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 = insertWith const

O(min(m,s)). Like insert, but the new value is reduced to weak head normal form before being placed into the map.

insert' = insertWith' const

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.

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.

O(min(m,s)). Removes the key from the map along with its associated value. If the key is not a member of the map, the map is unchanged.

O(min(m,s)). Updates the value at the given key: if the given function returns Nothing, the value and its associated key are removed; if Just a is returned, the old value is replaced with a. If the key is not a member of the map, the map is unchanged.

O(min(m,s)). Like update, but also returns Just the original value, or Nothing if the key is not a member of the map.

O(min(m,s)). Adjusts the value at the given key by calling the given function on it. If the key is not a member of the map, the map is unchanged.

O(min(m,s)). Like adjust, but the function is applied strictly.

O(min(m,s)). The most general modification function, allowing you to modify the value at the given key, whether or not it is a member of the map. In short: the given function is passed Just the value at the key if it is present, or Nothing otherwise; if the function returns Just a value, the new value is inserted into the map, otherwise the old value is removed. More precisely, for alter f k m:

If k is a member of m, f (Just oldValue) is called. Now:

• If f returned Just newValue, oldValue is replaced with newValue.
• If f returned Nothing, k and oldValue are removed from the map.

If, instead, k is not a member of m, f Nothing is called, and:

• If f returned Just value, value is inserted into the map, at k.
• If f returned Nothing, the map is unchanged.

The function is applied lazily only if the given key is a prefix of more than one key in the map.

O(min(m,s)). Like alter, but the function is always applied strictly.

O(1). True iff the map is empty.

O(n m). The number of elements in the map. The value is built up lazily, allowing for delivery of partial results without traversing the whole map.

O(n m). The number of elements in the map. The value is built strictly: no value is returned until the map has been fully traversed.

O(min(m,s)). True iff the given key is associated with a value in the map.

O(min(m,s)). False iff the given key is associated with a value in the map.

O(min(m,s)). Just the value in the map associated with the given key, or Nothing if the key is not a member of the map.

O(min(m,s)). Like lookup, but returns the given value when the key is not a member of the map.

O(min(n1 m1,n2 m2)). True iff the first map is a submap of the second, i.e. all keys that are members of the first map are also members of the second map, and their associated values are the same.

isSubmapOf = isSubmapOfBy (==)

O(min(n1 m1,n2 m2)). Like isSubmapOf, but one can specify the equality relation applied to the values.

True iff all keys that are members of the first map are also members of the second map, and the given function f returns True for all f firstMapValue secondMapValue where firstMapValue and secondMapValue are associated with the same key.

O(min(n1 m1,n2 m2)). True iff the first map is a proper submap of the second, i.e. all keys that are members of the first map are also members of the second map, and their associated values are the same, but the maps are not equal. That is, at least one key was a member of the second map but not the first.

isProperSubmapOf = isProperSubmapOfBy (==)

O(min(n1 m1,n2 m2)). Like isProperSubmapOf, but one can specify the equality relation applied to the values.

True iff all keys that are members of the first map are also members of the second map, and the given function f returns True for all f firstMapValue secondMapValue where firstMapValue and secondMapValue are associated with the same key, and at least one key in the second map is not a member of the first.

O(min(n1 m1,n2 m2)). The union of the two maps: the map which contains all keys that are members of either map. This union is left-biased: if a key is a member of both maps, the value from the first map is chosen.

The worst-case performance occurs when the two maps are identical.

union = unionWith const

O(min(n1 m1,n2 m2)). Like union, but the combining function (const) is applied strictly.

union' = unionWith' const

O(sum(n)). The union of all the maps: the map which contains all keys that are members of any of the maps. If a key is a member of multiple maps, the value that occurs in the earliest of the maps (according to the order of the given list) is chosen.

The worst-case performance occurs when all the maps are identical.

unions = unionsWith const

O(sum(n)). Like unions, but the combining function (const) is applied strictly.

unions' = unionsWith' const

O(min(n1 m1,n2 m2)). Like union, but the given function is used to determine the new value if a key is a member of both given maps. For a function f, the new value is f firstMapValue secondMapValue.

O(min(n1 m1,n2 m2)). Like unionWith, but in addition to the two values, the key is passed to the combining function.

O(sum(n)). Like unions, but the given function determines the final value if a key is a member of more than one map. The function is applied as a left fold over the values in the given list's order. For example:

unionsWith (-) [fromList [("a",1)],fromList [("a",2)],fromList [("a",3)]]
   == fromList [("a",(1-2)-3)]
   == fromList [("a",-4)]

O(sum(n)). Like unionsWith, but in addition to the two values under consideration, the key is passed to the combining function.

O(min(n1 m1,n2 m2)). Like unionWith, but the combining function is applied strictly.

O(min(n1 m1,n2 m2)). Like unionWithKey, but the combining function is applied strictly.

O(sum(n)). Like unionsWith, but the combining function is applied strictly.

O(sum(n)). Like unionsWithKey, but the combining function is applied strictly.

O(min(n1 m1,n2 m2)). The difference of the two maps: the map which contains all keys that are members of the first map and not of the second.

The worst-case performance occurs when the two maps are identical.

difference = differenceWith (\_ _ -> Nothing)

O(min(n1 m1,n2 m2)). Like difference, but the given function determines what to do when a key is a member of both maps. If the function returns Nothing, the key is removed; if it returns Just a new value, that value replaces the old one in the first map.

O(min(n1 m1,n2 m2)). Like differenceWith, but in addition to the two values, the key they are associated with is passed to the combining function.

O(min(n1 m1,n2 m2)). The intersection of the two maps: the map which contains all keys that are members of both maps.

The worst-case performance occurs when the two maps are identical.

intersection = intersectionWith const

O(min(n1 m1,n2 m2)). Like intersection, but the combining function is applied strictly.

intersection' = intersectionWith' const

O(min(n1 m1,n2 m2)). Like intersection, but the given function determines the new values.

O(min(n1 m1,n2 m2)). Like intersectionWith, but in addition to the two values, the key they are associated with is passed to the combining function.

O(min(n1 m1,n2 m2)). Like intersectionWith, but the combining function is applied strictly.

O(min(n1 m1,n2 m2)). Like intersectionWithKey, but the combining function is applied strictly.

O(n m). Apply the given function to the elements in the map, discarding those for which the function returns False.

O(n m). Like filter, but the key associated with the element is also passed to the given predicate.

O(n m). A pair of maps: the first element contains those values for which the given predicate returns True, and the second contains those for which it was False.

O(n m). Like partition, but the key associated with the element is also passed to the given predicate.

O(n m). Apply the given function to the elements in the map, preserving only the Just results.

O(n m). Like mapMaybe, but the key associated with the element is also passed to the given function.

O(n m). Apply the given function to the elements in the map, separating the Left results from the Right. The first element of the pair contains the former results, and the second the latter.

O(n m). Like mapEither, but the key associated with the element is also passed to the given function.

O(n m). Apply the given function to all the elements in the map.

O(n m). Like map, but apply the function strictly.

O(n m). Like map, but also pass the key associated with the element to the given function.

O(n m). Like mapWithKey, but apply the function strictly.

O(n m). Apply the given function to all the keys in a map.

mapKeys = mapKeysWith const

O(n m). Like mapKeys, but use the first given function to combine elements if the second function gives two keys the same value.

O(n m). Apply the given function to the contents of all the keys in the map.

mapInKeys = mapInKeysWith const

O(n m). Like mapInKeys, but combine identical keys strictly.

mapInKeys' = mapInKeysWith' const

O(n m). Like mapInKeys, but use the first given function to combine elements if the second function gives two keys the same value.

O(n m). Like mapInKeysWith, but apply the combining function strictly.

O(n m). Like Data.List.mapAccumL on the toList representation.

Essentially a combination of map and foldl: the given function is applied to each element of the map, resulting in a new value for the accumulator and a replacement element for the map.

O(n m). Like mapAccum, but the function receives the key in addition to the value associated with it.

O(n m). Like mapAccum, but the function is applied strictly.

O(n m). Like mapAccumWithKey, but the function is applied strictly.

O(n m). Like mapAccum, but in ascending order, as though operating on the toAscList representation.

O(n m). Like mapAccumAsc, but the function receives the key in addition to the value associated with it.

O(n m). Like mapAccumAsc, but the function is applied strictly.

O(n m). Like mapAccumAscWithKey, but the function is applied strictly.

O(n m). Like mapAccum, but in descending order, as though operating on the toDescList representation.

O(n m). Like mapAccumDesc, but the function receives the key in addition to the value associated with it.

O(n m). Like mapAccumDesc, but the function is applied strictly.

O(n m). Like mapAccumDescWithKey, but the function is applied strictly.

O(n m). Equivalent to a list foldr on the toList representation, folding only over the elements.

O(n m). Equivalent to a list foldr on the toList representation, folding over both the keys and the elements.

O(n m). Equivalent to a list foldr on the toAscList representation.

O(n m). Equivalent to a list foldr on the toAscList representation, folding over both the keys and the elements.

O(n m). Equivalent to a list foldr on the toDescList representation.

O(n m). Equivalent to a list foldr on the toDescList representation, folding over both the keys and the elements.

O(n m). Equivalent to a list foldl on the toList representation.

O(n m). Equivalent to a list foldl on the toList representation, folding over both the keys and the elements.

O(n m). Equivalent to a list foldl on the toAscList representation.

O(n m). Equivalent to a list foldl on the toAscList representation, folding over both the keys and the elements.

O(n m). Equivalent to a list foldl on the toDescList representation.

O(n m). Equivalent to a list foldl on the toDescList representation, folding over both the keys and the elements.

O(n m). Equivalent to a list foldl' on the toList representation.

O(n m). Equivalent to a list foldl' on the toList representation, folding over both the keys and the elements.

O(n m). Equivalent to a list foldl' on the toAscList representation.

O(n m). Equivalent to a list foldl' on the toAscList representation, folding over both the keys and the elements.

O(n m). Equivalent to a list foldl' on the toDescList representation.

O(n m). Equivalent to a list foldl' on the toDescList representation, folding over both the keys and the elements.

O(n m). Converts the map to a list of the key-value pairs contained within, in undefined order.

O(n m). Converts the map to a list of the key-value pairs contained within, in ascending order.

O(n m). Converts the map to a list of the key-value pairs contained within, in descending order.

O(n m). Creates a map from a list of key-value pairs. If a key occurs more than once, the value from the last pair (according to the list's order) is the one which ends up in the map.

fromList = fromListWith const

O(n m). Like fromList, but the given function is used to determine the final value if a key occurs more than once. The function is applied as though it were flipped and then applied as a left fold over the values in the given list's order. Or, equivalently (except as far as performance is concerned), as though the function were applied as a right fold over the values in the reverse of the given list's order. For example:

fromListWith (-) [("a",1),("a",2),("a",3),("a",4)]
   == fromList [("a",4-(3-(2-1)))]
   == fromList [("a",2)]

O(n m). Like fromListWith, but the key, in addition to the values to be combined, is passed to the combining function.

O(n m). Like fromListWith, but the combining function is applied strictly.

O(n m). Like fromListWithKey, but the combining function is applied strictly.

O(m). Removes and returns the minimal key in the map, along with the value associated with it. If the map is empty, Nothing and the original map are returned.

O(m). Removes and returns the maximal key in the map, along with the value associated with it. If the map is empty, Nothing and the original map are returned.

O(m). Like fst composed with minView. Just the minimal key in the map and its associated value, or Nothing if the map is empty.

O(m). Like fst composed with maxView. Just the minimal key in the map and its associated value, or Nothing if the map is empty.

O(m). Like snd composed with minView. The map without its minimal key, or the unchanged original map if it was empty.

O(m). Like snd composed with maxView. The map without its maximal key, or the unchanged original map if it was empty.

O(min(m,s)). Splits the map in two about the given key. The first element of the resulting pair is a map containing the keys lesser than the given key; the second contains those keys that are greater.

O(min(m,s)). Like split, but also returns the value associated with the given key, if any.

O(m). Just the key of the map which precedes the given key in order, along with its associated value, or Nothing if the map is empty.

O(m). Just the key of the map which succeeds the given key in order, along with its associated value, or Nothing if the map is empty.

O(s). The map which contains all keys of which the given key is a prefix. For example:

lookupPrefix "ab" (fromList [("a",1),("ab",2),("ac",3),("abc",4)])
   == fromList [("ab",2),("abc",4)]

O(s). Prepends the given key to all the keys of the map. For example:

addPrefix "xa" (fromList [("a",1),("b",2)])
   == fromList [("xaa",1),("xab",2)]

O(s). The map which contains all keys of which the given key is a prefix, with the prefix removed from each key. If the given key is not a prefix of any key in the map, an empty map is returned. For example:

deletePrefix "a" (fromList [("a",1),("ab",2),("ac",3)])
   == fromList [("",1),("b",2),("c",3)]

This function can be used, for instance, to reduce potentially expensive I/O operations: if you need to find the value in a map associated with a string, but you only have a prefix of it and retrieving the rest is an expensive operation, calling deletePrefix with what you have might allow you to avoid the operation: if the resulting map is empty, the entire string cannot be a member of the map.

O(s). Deletes all keys which are suffixes of the given key. For example:

deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])
   == fromList [("a",1),("ac",3),("b",4)]

O(1). A triple containing the longest common prefix of all keys in the map, the value associated with that prefix, if any, and the map with that prefix removed from all the keys as well as the map itself. Examples:

splitPrefix (fromList [("a",1),("b",2)])
   == ("", Nothing, fromList [("a",1),("b",2)])
splitPrefix (fromList [("a",1),("ab",2),("ac",3)])
   == ("a", Just 1, fromList [("b",2),("c",3)])

O(1). The children of the longest common prefix in the trie as maps, associated with their distinguishing key value. If the map contains less than two keys, this function will return an empty map. Examples;

children (fromList [("a",1),("abc",2),("abcd",3)])
   == Map.fromList [('b',fromList [("c",2),("cd",3)])]
children (fromList [("b",1),("c",2)])
   == Map.fromList [('b',fromList [("",1)]),('c',fromList [("",2)])]

O(1). The children of the first element of the longest common prefix in the trie as maps, associated with their distinguishing key value. If the map contains less than two keys, this function will return an empty map.

If the longest common prefix of all keys in the trie is the empty list, this function is equivalent to children.

Examples:

children1 (fromList [("abc",1),("abcd",2)])
   == Map.fromList [('a',fromList [("bc",1),("bcd",2)])]
children1 (fromList [("b",1),("c",2)])
   == Map.fromList [('b',fromList [("",1)]),('c',fromList [("",2)])]

O(n m). Displays the map's internal structure in an undefined way. That is to say, no program should depend on the function's results.

O(n m). Like showTrie, but uses the given function to display the elements of the map. Still undefined.