Data.ListTrie.Set.Ord

A set of lists of elements that can be totally ordered, based on a trie.

Documentation

type TrieSet = TrieSet Map

empty :: Map map a => TrieSet map a

O(1). The empty set.

singleton :: Map map a => [a] -> TrieSet map a

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

insert :: Map map a => [a] -> TrieSet map a -> TrieSet map a

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

delete :: Map map a => [a] -> TrieSet map a -> TrieSet map a

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

null :: Map map a => TrieSet map a -> Bool

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

size :: (Map map a, Num n) => TrieSet map a -> n

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.

size' :: (Map map a, Num n) => TrieSet map a -> n

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.

member :: Map map a => [a] -> TrieSet map a -> Bool

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

notMember :: Map map a => [a] -> TrieSet map a -> Bool

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

isSubsetOf :: Map map a => TrieSet map a -> TrieSet map a -> Bool

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.

isProperSubsetOf :: Map map a => TrieSet map a -> TrieSet map a -> Bool

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.

union :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a

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.

unions :: Map map a => [TrieSet map a] -> TrieSet map a

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.

difference :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a

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.

intersection :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a

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.

filter :: Map map a => ([a] -> Bool) -> TrieSet map a -> TrieSet map a

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

partition :: Map map a => ([a] -> Bool) -> TrieSet map a -> (TrieSet map a, TrieSet map a)

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.

map :: (Map map a, Map map b) => ([a] -> [b]) -> TrieSet map a -> TrieSet map b

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

mapIn :: (Map map a, Map map b) => (a -> b) -> TrieSet map a -> TrieSet map b

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

foldr :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

foldrAsc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

foldrDesc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

foldl :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

foldlAsc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

foldlDesc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

foldl' :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

foldlAsc' :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

foldlDesc' :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b

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

toList :: Map map a => TrieSet map a -> [[a]]

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

toAscList :: OrdMap map a => TrieSet map a -> [[a]]

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

toDescList :: OrdMap map a => TrieSet map a -> [[a]]

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

fromList :: Map map a => [[a]] -> TrieSet map a

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

minView :: OrdMap map a => TrieSet map a -> (Maybe [a], TrieSet map a)

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

maxView :: OrdMap map a => TrieSet map a -> (Maybe [a], TrieSet map a)

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

findMin :: OrdMap map a => TrieSet map a -> Maybe [a]

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

findMax :: OrdMap map a => TrieSet map a -> Maybe [a]

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

deleteMin :: OrdMap map a => TrieSet map a -> TrieSet map a

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

deleteMax :: OrdMap map a => TrieSet map a -> TrieSet map a

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

split :: OrdMap map a => [a] -> TrieSet map a -> (TrieSet map a, TrieSet map a)

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.

splitMember :: OrdMap map a => [a] -> TrieSet map a -> (TrieSet map a, Bool, TrieSet map a)

O(min(m,s)). Like split, but also returns whether the given key was a member of the set or not.

findPredecessor :: OrdMap map a => [a] -> TrieSet map a -> Maybe [a]

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

findSuccessor :: OrdMap map a => [a] -> TrieSet map a -> Maybe [a]

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

lookupPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a

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

addPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a

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

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

deletePrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a

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.

deleteSuffixes :: Map map a => [a] -> TrieSet map a -> TrieSet map a

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

splitPrefix :: Map map a => TrieSet map a -> ([a], Bool, TrieSet map a)

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

children :: Map map a => TrieSet map a -> map a (TrieSet map a)

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

children1 :: Map map a => TrieSet map a -> map a (TrieSet map a)

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

showTrie :: (Show a, Map map a) => TrieSet map a -> ShowS

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.