Data.Trie.Pred

A "predicative" trie is a lookup table where you can embed arbitrary predicates as a method to satisfy a node as "found" - this is done with existential quantification. To embed our predicates, we need to build the trie's data constructors manually, to unify the existential data with the the result function.

As a botched example, you could imagine a "step" of the trie structure as something like this:

PredTrie s a
  = PNil
  | forall t. PCons
      { predicate :: s -> Maybe t
      , result    :: t -> a
      }

This isn't how it's actually represented, of course - this doesn't acocunt for literal matches (i.e. enumerated results).

Predicated Trie

data PredTrie s a

Constructors

PredTrie

Fields

predLits :: HashMapStep PredTrie s a

a literal step

predPreds :: PredSteps PredTrie s a

a predicative step

Instances

(Hashable s, Eq s) => Trie NonEmpty s PredTrie

Functor (PredTrie s)

Show (PredTrie s a)

Dummy instance for quickcheck

(Hashable s, Eq s) => Monoid (PredTrie s a)

(Arbitrary s, Arbitrary a, Eq s, Hashable s) => Arbitrary (PredTrie s a)

emptyPT :: PredTrie s a

matchPT :: (Hashable s, Eq s) => NonEmpty s -> PredTrie s a -> Maybe (NonEmpty s, a, [s])

Find the nearest parent node of the requested query, while returning the split of the string that was matched, and what wasn't.

matchesPT :: (Hashable s, Eq s) => NonEmpty s -> PredTrie s a -> [(NonEmpty s, a, [s])]

Rooted Predicated Trie

data RootedPredTrie s a

Constructors

RootedPredTrie

Fields

rootedBase :: Maybe a

The "root" node - the path at []

rootedSub :: PredTrie s a

The actual predicative trie

Instances

(Hashable s, Eq s) => Trie [] s RootedPredTrie

Functor (RootedPredTrie s)

(Hashable s, Eq s) => Monoid (RootedPredTrie s a)

emptyRPT :: RootedPredTrie s a

matchRPT :: (Hashable s, Eq s) => [s] -> RootedPredTrie s a -> Maybe ([s], a, [s])

matchesRPT :: (Hashable s, Eq s) => [s] -> RootedPredTrie s a -> [([s], a, [s])]