list-tries-0.2: Tries and Patricia tries: finite sets and maps for list keys

Data.ListTrie.Patricia.Set

Description

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

Worst-case complexities are given in terms of `n`, `m`, and `k`. `n` refers to the number of keys in the set and `m` to their maximum length. `k` 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.

Synopsis

# Set type

data TrieSet map a Source

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), Map map a) => Eq (TrieSet map a) (Eq (CMap map a Bool), OrdMap map a, Ord a) => Ord (TrieSet map a) (Map map a, Read a) => Read (TrieSet map a) (Map map a, Show a) => Show (TrieSet map a) Map map a => Monoid (TrieSet map a) (Map map a, Binary a) => Binary (TrieSet map a)

# Construction

empty :: Map map a => TrieSet map aSource

`O(1)`. The empty set.

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

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

# Modification

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

`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 aSource

`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 -> BoolSource

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

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

`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 -> nSource

`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 -> BoolSource

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

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

`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 -> BoolSource

`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 -> BoolSource

`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 aSource

`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 aSource

`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 aSource

`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 aSource

`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 aSource

`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)Source

`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 bSource

`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 bSource

`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 -> bSource

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

`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]]Source

`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]]Source

`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]]Source

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

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

`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)Source

`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)Source

`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]Source

`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]Source

`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 aSource

`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 aSource

`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)Source

`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)Source

`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]Source

`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]Source

`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.

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

`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 aSource

`O(m)`. 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, the set is returned unchanged. 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.

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

`O(1)`. 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 -> [(a, TrieSet map a)]Source

`O(1)`. 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 the empty list. Examples;

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

# Visualization

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

`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.