Copyright | (c) 2015 Athan Clark |
---|---|
License | BSD-3 |
Maintainer | athan.clark@gmail.com |
Stability | experimental |
Portability | GHC |
Safe Haskell | None |
Language | Haskell2010 |
A "predicative" trie is a lookup table where you can use predicates as a method to match a query path, where success is also enriched with any auxiliary data. This library allows you to match a path-chunk (if you consider a query to the different levels of the tree as a list) with a Boolean predicate, augmented with existentially quantified data. This lets us use parsers, regular expressions, and other functions that can be turned into the form of:
forall a. p -> Maybe a
However, because the communicated data is existentially quantified, we cannot
revisit a definition - we cannot update
a predicative node, or change any of
its children. The current version of this library forces you to use PredTrie
and RootedPredTrie
directly (i.e. the data constructors) to build your trie
manually.
This isn't the actual code, but it's a general idea for how you could build a
trie. We build a "tagged" rose-tree,
where each node has either a literal name (and is a singleton of the k
type in our
lookup path) or a predicate to consider the current node or its children as the target.
You could imagine a "step" of the trie structure as something like this:
data PredTrie k a = Nil | Lit { litTag :: k , litResult :: Maybe a , litChildren :: Maybe (PredTrie k a) } | forall t. Pred { predMatch :: k -> Maybe t , predResult :: Maybe (t -> a) , predChildren :: Maybe (PredTrie k a) }
Notice how in the Pred
constructor, we first create the t
data in predMatch
,
then consume it in predResult
. We make a tree out of steps by recursing over the
steps.
This isn't how it's actually represented internally, but serves to help see the representation. If you want to build tries and perform lookups casually, please see the Data.Trie.Pred.Interface module.
- data PredTrie k a = PredTrie {}
- emptyPT :: PredTrie k a
- matchPT :: (Hashable k, Eq k) => NonEmpty k -> PredTrie k a -> Maybe (NonEmpty k, a, [k])
- matchesPT :: (Hashable k, Eq k) => NonEmpty k -> PredTrie k a -> [(NonEmpty k, a, [k])]
- data RootedPredTrie k a = RootedPredTrie {
- rootedBase :: !(Maybe a)
- rootedSub :: !(PredTrie k a)
- emptyRPT :: RootedPredTrie k a
- matchRPT :: (Hashable k, Eq k) => [k] -> RootedPredTrie k a -> Maybe ([k], a, [k])
- matchesRPT :: (Hashable k, Eq k) => [k] -> RootedPredTrie k a -> [([k], a, [k])]
Predicated Trie
matchPT :: (Hashable k, Eq k) => NonEmpty k -> PredTrie k a -> Maybe (NonEmpty k, a, [k]) Source #
Find the nearest parent node of the requested query, while returning the split of the string that was matched, and what wasn't.
Rooted Predicative Trie
data RootedPredTrie k a Source #
RootedPredTrie | |
|
(Hashable k, Eq k) => Trie [] k RootedPredTrie Source # | |
Functor (RootedPredTrie k) Source # | |
(Show k, Show a) => Show (RootedPredTrie k a) Source # | |
(Hashable k, Eq k) => Monoid (RootedPredTrie k a) Source # | |
Singleton (PathChunks k ([] (Maybe *))) a (RootedPredTrie k a) Source # | |
Extrude (PathChunks k ([] (Maybe *))) (RootedPredTrie k a) (RootedPredTrie k a) Source # | |
(Eq k, Hashable k, Typeable * r) => Extend (PathChunk k (Just * r)) (RootedPredTrie k (r -> a)) (RootedPredTrie k a) Source # | Existentially quantified case |
(Eq k, Hashable k) => Extend (PathChunk k (Nothing *)) (RootedPredTrie k a) (RootedPredTrie k a) Source # | Literal case |
Monad m => MonadState (RootedPredTrie k v) (PTBuilderT k v m) | |
(Monad m, Eq k, Hashable k) => MonadWriter (RootedPredTrie k v) (PTBuilderT k v m) | |
emptyRPT :: RootedPredTrie k a Source #
matchesRPT :: (Hashable k, Eq k) => [k] -> RootedPredTrie k a -> [([k], a, [k])] Source #