Data.Trie.Set

This module provides a type TSet c, which is a set of list of some characters. It serves almost same purpose to Set [c], and functions of this module mirrors functions with same name from Data.Set module.

The advantages to use this module over Data.Set are:

• Faster member.
• Partial match provided by beginWith function.
• Efficient append, prefixes, and suffixes functions.

But notice for some disadvantages:

• Some operations are slower than Set [c]. Especially, count is much much slower than size (because Set.size is already recorded in the data structure). Consider TSet.count be like length of list.
• Constructed TSet c from a list of lists [[c]] do not share each member lists with original list unlike Set [c] does. This means holding both TSet c and [[c]] in memory consumes much more memory than Set [c] and [[c]].

Types

data TSet c

Instances

Eq c => Eq (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

(==) :: TSet c -> TSet c -> Bool

(/=) :: TSet c -> TSet c -> Bool

Ord c => Ord (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

compare :: TSet c -> TSet c -> Ordering

(<) :: TSet c -> TSet c -> Bool

(<=) :: TSet c -> TSet c -> Bool

(>) :: TSet c -> TSet c -> Bool

(>=) :: TSet c -> TSet c -> Bool

max :: TSet c -> TSet c -> TSet c

min :: TSet c -> TSet c -> TSet c

Show c => Show (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

showsPrec :: Int -> TSet c -> ShowS

show :: TSet c -> String

showList :: [TSet c] -> ShowS

Ord c => Semigroup (TSet c)

Semigroup(union)

Defined in Data.Trie.Set.Hidden

Methods

(<>) :: TSet c -> TSet c -> TSet c

sconcat :: NonEmpty (TSet c) -> TSet c

stimes :: Integral b => b -> TSet c -> TSet c

Ord c => Monoid (TSet c)

Monoid(empty, union)

Defined in Data.Trie.Set.Hidden

Methods

mempty :: TSet c

mappend :: TSet c -> TSet c -> TSet c

mconcat :: [TSet c] -> TSet c

NFData c => NFData (TSet c)

Defined in Data.Trie.Set.Hidden

Methods

rnf :: TSet c -> ()

Queries

member :: Ord c => [c] -> TSet c -> Bool

notMember :: Ord c => [c] -> TSet c -> Bool

beginWith :: Ord c => TSet c -> [c] -> TSet c

beginWith t xs returns new TSet t' which contains all string ys such that t contains xs ++ ys.

null :: TSet c -> Bool

count :: TSet c -> Int

Returns number of elements. count takes O(number of nodes) unlike size which is O(1).

enumerate :: TSet c -> [[c]]

List of all elements.

foldMap :: Monoid r => ([c] -> r) -> TSet c -> r

foldr :: ([c] -> r -> r) -> r -> TSet c -> r

foldl' :: (r -> [c] -> r) -> r -> TSet c -> r

Construction

empty :: TSet c

epsilon :: TSet c

epsilon = singleton []

singleton :: [c] -> TSet c

insert :: (Ord c, Foldable f) => f c -> TSet c -> TSet c

delete :: (Ord c, Foldable f) => f c -> TSet c -> TSet c

Combine

union :: Ord c => TSet c -> TSet c -> TSet c

intersection :: Ord c => TSet c -> TSet c -> TSet c

difference :: Ord c => TSet c -> TSet c -> TSet c

append :: Ord c => TSet c -> TSet c -> TSet c

Other operations

prefixes :: TSet c -> TSet c

suffixes :: Ord c => TSet c -> TSet c

infixes :: Ord c => TSet c -> TSet c

Conversion

fromList :: Ord c => [[c]] -> TSet c

toList :: TSet c -> [[c]]

fromAscList :: Eq c => [[c]] -> TSet c

toAscList :: TSet c -> [[c]]

fromSet :: Eq c => Set [c] -> TSet c

toSet :: TSet c -> Set [c]

Parsing

toParser

Arguments

:: Alternative f

=> (c -> f a)

char

-> f b

eot

-> TSet c

-> f [a]

Construct a "parser" which recognizes member strings of a TSet.

• char constructs a parser which recognizes a character.
• eot recognizes the end of a token.

toParser_

Arguments

:: Alternative f

=> (c -> f a)

char

-> f b

eot

-> TSet c

-> f ()

Construct a "parser" which recognizes member strings of a TSet. It discards the information which string it is recognizing.

• char constructs a parser which recognizes a character.
• eot recognizes the end of a token.