Safe Haskell | None |
---|---|

Language | Haskell98 |

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

- data TrieSet map a
- empty :: Map map a => TrieSet map a
- singleton :: Map map a => [a] -> TrieSet map a
- insert :: Map map a => [a] -> TrieSet map a -> TrieSet map a
- delete :: Map map a => [a] -> TrieSet map a -> TrieSet map a
- null :: Map map a => TrieSet map a -> Bool
- size :: (Map map a, Num n) => TrieSet map a -> n
- size' :: (Map map a, Num n) => TrieSet map a -> n
- member :: Map map a => [a] -> TrieSet map a -> Bool
- notMember :: Map map a => [a] -> TrieSet map a -> Bool
- isSubsetOf :: Map map a => TrieSet map a -> TrieSet map a -> Bool
- isProperSubsetOf :: Map map a => TrieSet map a -> TrieSet map a -> Bool
- union :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a
- unions :: Map map a => [TrieSet map a] -> TrieSet map a
- difference :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a
- intersection :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a
- filter :: Map map a => ([a] -> Bool) -> TrieSet map a -> TrieSet map a
- partition :: Map map a => ([a] -> Bool) -> TrieSet map a -> (TrieSet map a, TrieSet map a)
- map :: (Map map a, Map map b) => ([a] -> [b]) -> TrieSet map a -> TrieSet map b
- mapIn :: (Map map a, Map map b) => (a -> b) -> TrieSet map a -> TrieSet map b
- foldr :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- foldrAsc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- foldrDesc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- foldl :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- foldlAsc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- foldlDesc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- foldl' :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- foldlAsc' :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- foldlDesc' :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
- toList :: Map map a => TrieSet map a -> [[a]]
- toAscList :: OrdMap map a => TrieSet map a -> [[a]]
- toDescList :: OrdMap map a => TrieSet map a -> [[a]]
- fromList :: Map map a => [[a]] -> TrieSet map a
- minView :: OrdMap map a => TrieSet map a -> (Maybe [a], TrieSet map a)
- maxView :: OrdMap map a => TrieSet map a -> (Maybe [a], TrieSet map a)
- findMin :: OrdMap map a => TrieSet map a -> Maybe [a]
- findMax :: OrdMap map a => TrieSet map a -> Maybe [a]
- deleteMin :: OrdMap map a => TrieSet map a -> TrieSet map a
- deleteMax :: OrdMap map a => TrieSet map a -> TrieSet map a
- split :: OrdMap map a => [a] -> TrieSet map a -> (TrieSet map a, TrieSet map a)
- splitMember :: OrdMap map a => [a] -> TrieSet map a -> (TrieSet map a, Bool, TrieSet map a)
- findPredecessor :: OrdMap map a => [a] -> TrieSet map a -> Maybe [a]
- findSuccessor :: OrdMap map a => [a] -> TrieSet map a -> Maybe [a]
- lookupPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a
- addPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a
- deletePrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a
- deleteSuffixes :: Map map a => [a] -> TrieSet map a -> TrieSet map a
- splitPrefix :: Map map a => TrieSet map a -> ([a], Bool, TrieSet map a)
- children :: Map map a => TrieSet map a -> map a (TrieSet map a)
- children1 :: Map map a => TrieSet map a -> map a (TrieSet map a)
- showTrie :: (Show a, Map map a) => TrieSet map a -> ShowS

# Set type

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`

.

(Eq (CMap map a Bool), Map map a) => Eq (TrieSet map a) Source # | |

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

(Map map a, Read a) => Read (TrieSet map a) Source # | |

(Map map a, Show a) => Show (TrieSet map a) Source # | |

Map map a => Semigroup (TrieSet map a) Source # | |

Map map a => Monoid (TrieSet map a) Source # | |

(Map map a, Binary a) => Binary (TrieSet map a) Source # | |

# Construction

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

`O(1)`

. The singleton set containing only the given key.

# Modification

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

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

`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

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

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

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

`O(min(m,s))`

. `True`

iff the given key is contained within the set.

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

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

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

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

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

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

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

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

`O(n m)`

. The set of those keys in the set for which the given predicate
returns `True`

.

# Mapping

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

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

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

`O(n m)`

. Equivalent to a list `foldr`

on the `toList`

representation.

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

`O(n m)`

. Equivalent to a list `foldr`

on the `toAscList`

representation.

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

`O(n m)`

. Equivalent to a list `foldr`

on the `toDescList`

representation.

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

`O(n m)`

. Equivalent to a list `foldl`

on the `toList`

representation.

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

`O(n m)`

. Equivalent to a list `foldl`

on the `toAscList`

representation.

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

`O(n m)`

. Equivalent to a list `foldl`

on the `toDescList`

representation.

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

`O(n m)`

. Equivalent to a list `foldl'`

on the `toList`

representation.

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

`O(n m)`

. Equivalent to a list `foldl'`

on the `toAscList`

representation.

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

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

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

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

# 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 Source #

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

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

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

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

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