Data.ListTrie.Set

The base implementation of a trie representing a set of lists, generalized over any type of map from key values to tries.

Worst-case complexities are given in terms of n, m, and s. n refers to the number of keys in the set and m to their maximum length. s refers to the length of a key given to the function, not any property of the set.

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.

Set type

data TrieSet map a

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.

Instances

Eq (CMap map a Bool) => Eq (TrieSet map a)

Methods

(==) :: TrieSet map a -> TrieSet map a -> Bool

(/=) :: TrieSet map a -> TrieSet map a -> Bool

(Eq (CMap map a Bool), OrdMap map a, Ord a) => Ord (TrieSet map a)

Methods

compare :: TrieSet map a -> TrieSet map a -> Ordering

(<) :: TrieSet map a -> TrieSet map a -> Bool

(<=) :: TrieSet map a -> TrieSet map a -> Bool

(>) :: TrieSet map a -> TrieSet map a -> Bool

(>=) :: TrieSet map a -> TrieSet map a -> Bool

max :: TrieSet map a -> TrieSet map a -> TrieSet map a

min :: TrieSet map a -> TrieSet map a -> TrieSet map a

(Map map a, Read a) => Read (TrieSet map a)

Methods

readsPrec :: Int -> ReadS (TrieSet map a)

readList :: ReadS [TrieSet map a]

readPrec :: ReadPrec (TrieSet map a)

readListPrec :: ReadPrec [TrieSet map a]

(Map map a, Show a) => Show (TrieSet map a)

Methods

showsPrec :: Int -> TrieSet map a -> ShowS

show :: TrieSet map a -> String

showList :: [TrieSet map a] -> ShowS

Map map a => Semigroup (TrieSet map a)

Methods

(<>) :: TrieSet map a -> TrieSet map a -> TrieSet map a

sconcat :: NonEmpty (TrieSet map a) -> TrieSet map a

stimes :: Integral b => b -> TrieSet map a -> TrieSet map a

Map map a => Monoid (TrieSet map a)

Methods

mempty :: TrieSet map a

mappend :: TrieSet map a -> TrieSet map a -> TrieSet map a

mconcat :: [TrieSet map a] -> TrieSet map a

(Map map a, Binary a) => Binary (TrieSet map a)

Methods

put :: TrieSet map a -> Put

get :: Get (TrieSet map a)

putList :: [TrieSet map a] -> Put

Construction

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.

Modification

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.

Querying

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.

Subsets

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.

Combination

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.

Filtering

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.

Mapping

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.

Folding

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.

Conversion to and from lists

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.

Ordering-sensitive operations

Minimum and maximum

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.

Predecessor and successor

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.

Trie-specific operations

Functions which utilize the unique structure of tries.

addPrefix and deletePrefix allow fast adding and removing of prefixes to/from all keys of a trie.

splitPrefix and children allow traversing of a trie in a manner suitable for its structure.

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

Visualization

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.