The data structure itself: a set of keys of type [a] implemented as a trie, using map to map keys of type a to sub-tries.

Regarding the instances:

• The CMap type is internal, ignore it. For Eq and Ord an Eq instance is required: what this means is that map a v is expected to be an instance of Eq, given Eq v.
• The Eq constraint for the Ord instance is misleading: it is needed only because Eq is a superclass of Ord.
• The Monoid instance defines mappend as union and mempty as empty.

O(1). The empty set.

O(s). The singleton set containing only the given key.

O(min(m,s)). Inserts the key into the set. If the key is already a member of the set, the set is unchanged.

O(min(m,s)). Removes the key from the set. If the key is not a member of the set, the set is unchanged.

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

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

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

O(min(m,s)). True iff the given key is contained within the set.

O(min(m,s)). False iff the given key is contained within the set.

O(min(n1 m1,n2 m2)). True iff the first set is a subset of the second, i.e. all keys that are members of the first set are also members of the second set.

O(min(n1 m1,n2 m2)). True iff the first set is a proper subset of the second, i.e. the first is a subset of the second, but the sets are not equal.

O(min(n1 m1,n2 m2)). The union of the two sets: the set which contains all keys that are members of either set.

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

O(sum(n)). The union of all the sets: the set which contains all keys that are members of any of the sets.

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

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

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

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

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

O(n m). The set of those keys in the set for which the given predicate returns True.

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

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

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

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

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

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

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

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

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

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

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

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

O(n m). Converts the set to a list of the keys contained within, in undefined order.

O(n m). Converts the set to a list of the keys contained within, in ascending order.

O(n m). Converts the set to a list of the keys contained within, in descending order.

O(n m). Creates a set from a list of keys.

O(m). Removes and returns the minimal key in the set. If the set is empty, Nothing and the original set are returned.

O(m). Removes and returns the maximal key in the set. If the set is empty, Nothing and the original set are returned.

O(m). Like fst composed with minView. Just the minimal key in the set, or Nothing if the set is empty.

O(m). Like fst composed with maxView. Just the maximal key in the set, or Nothing if the set is empty.

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

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

O(min(m,s)). Splits the set in two about the given key. The first element of the resulting pair is a set 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 whether the given key was a member of the set or not.

O(m). Just the key of the set which precedes the given key in order, or Nothing if the set is empty.

O(m). Just the key of the set which succeeds the given key in order, or Nothing if the set is empty.

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

lookupPrefix "ab" (fromList ["a","ab","ac","abc"])
   == fromList ["ab","abc"]

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

addPrefix "pre" (fromList ["a","b"]) == fromList ["prea","preb"]

O(s). The set 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 set, an empty set is returned. For example:

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

This function can be used, for instance, to reduce potentially expensive I/O operations: if you need to check whether a string is a member of a set, 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 set is empty, the entire string cannot be a member of the set.

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(m). A triple containing the longest common prefix of all keys in the set, whether that prefix was a member of the set, and the set with that prefix removed from all the keys as well as the set itself. Examples:

splitPrefix (fromList ["a","b"]) == ("", False, fromList ["a","b"])
splitPrefix (fromList ["a","ab","ac"]) == ("a", True, fromList ["b","c"])

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

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

O(1). The children of the first element of the longest common prefix in the trie as sets, associated with their distinguishing key value. If the set 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","abcd"])
   == Map.fromList [('a',fromList ["bc","bcd"])]
children1 (fromList ["b","c"])
   == Map.fromList [('b',fromList [""]),('c',fromList [""])]

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