-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Various trie implementations in Haskell
--   
--   Various trie implementations in Haskell
@package tries
@version 0.0.2

module Data.Trie.Pseudo

-- | Tagged rose tree with explicit emptyness
data PseudoTrie t a
More :: t -> (Maybe a) -> (NonEmpty (PseudoTrie t a)) -> PseudoTrie t a
Rest :: (NonEmpty t) -> a -> PseudoTrie t a
Nil :: PseudoTrie t a

-- | Overwriting instance
beginsWith :: (Eq t) => PseudoTrie t a -> t -> Bool

-- | Provides a form of deletion by setting a path to <tt>Nothing</tt>, but
--   doesn't cleanup like <tt>prune</tt>
assign :: (Eq t) => NonEmpty t -> Maybe a -> PseudoTrie t a -> PseudoTrie t a

-- | Overwrite the LHS point-wise with the RHS's contents
merge :: (Eq t) => PseudoTrie t a -> PseudoTrie t a -> PseudoTrie t a
add :: (Eq t) => NonEmpty t -> PseudoTrie t a -> PseudoTrie t a -> PseudoTrie t a
toAssocs :: PseudoTrie t a -> [(NonEmpty t, a)]
fromAssocs :: (Eq t) => [(NonEmpty t, a)] -> PseudoTrie t a
lookup :: (Eq t) => NonEmpty t -> PseudoTrie t a -> Maybe a

-- | Simple test on the heads of two tries
areDisjoint :: (Eq t) => PseudoTrie t a -> PseudoTrie t a -> Bool

-- | The meet of two <tt>PseudoTrie</tt>s
intersectionWith :: (Eq t) => (a -> b -> c) -> PseudoTrie t a -> PseudoTrie t b -> PseudoTrie t c

-- | Needless intermediary elements are turned into shortcuts,
--   <tt>Nil</tt>'s in subtrees are also removed.
prune :: PseudoTrie t a -> PseudoTrie t a
instance Data.Traversable.Traversable (Data.Trie.Pseudo.PseudoTrie t)
instance Data.Foldable.Foldable (Data.Trie.Pseudo.PseudoTrie t)
instance GHC.Base.Functor (Data.Trie.Pseudo.PseudoTrie t)
instance (GHC.Classes.Eq t, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Trie.Pseudo.PseudoTrie t a)
instance (GHC.Show.Show t, GHC.Show.Show a) => GHC.Show.Show (Data.Trie.Pseudo.PseudoTrie t a)
instance GHC.Classes.Eq t => GHC.Base.Monoid (Data.Trie.Pseudo.PseudoTrie t a)

module Data.Trie.Class

-- | Class representing tries with single-threaded insertion, deletion, and
--   lookup. <tt>forall ts ps a. isJust $ lookupPath ps (insertPath ps a
--   ts)</tt> <tt>forall ts ps. isNothing $ lookupPath ps (deletePath ps
--   ts)</tt>
class Trie p s t | t -> p
lookup :: Trie p s t => p s -> t s a -> Maybe a
insert :: Trie p s t => p s -> a -> t s a -> t s a
delete :: Trie p s t => p s -> t s a -> t s a
lookupWithDefault :: Trie p s t => a -> p s -> t s a -> a
member :: Trie p s t => p s -> t s a -> Bool
notMember :: Trie p s t => p s -> t s a -> Bool
fromFoldable :: (Foldable f, Monoid (t s a), Trie p s t) => f (p s, a) -> t s a

-- | Embeds an empty ByteString passed around for type inference.
newtype BSTrie q a
BSTrie :: (q, Trie a) -> BSTrie q a
[unBSTrie] :: BSTrie q a -> (q, Trie a)
makeBSTrie :: Trie a -> BSTrie ByteString a
getBSTrie :: BSTrie ByteString a -> Trie a
instance Data.Trie.Class.Trie Data.Functor.Identity.Identity Data.ByteString.Internal.ByteString Data.Trie.Class.BSTrie

module Data.Trie.Knuth
newtype KnuthTrie s x
KnuthTrie :: KnuthForest (s, Maybe x) -> KnuthTrie s x
[unKnuthTrie] :: KnuthTrie s x -> KnuthForest (s, Maybe x)
instance (Test.QuickCheck.Arbitrary.Arbitrary s, Test.QuickCheck.Arbitrary.Arbitrary x) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.Knuth.KnuthTrie s x)
instance Data.Traversable.Traversable (Data.Trie.Knuth.KnuthTrie s)
instance Data.Foldable.Foldable (Data.Trie.Knuth.KnuthTrie s)
instance GHC.Base.Functor (Data.Trie.Knuth.KnuthTrie s)
instance (GHC.Classes.Eq s, GHC.Classes.Eq x) => GHC.Classes.Eq (Data.Trie.Knuth.KnuthTrie s x)
instance (GHC.Show.Show s, GHC.Show.Show x) => GHC.Show.Show (Data.Trie.Knuth.KnuthTrie s x)
instance GHC.Classes.Eq s => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s Data.Trie.Knuth.KnuthTrie

module Data.Trie.List
newtype ListTrie t x
ListTrie :: Tree (t, Maybe x) -> ListTrie t x
[unListTrie] :: ListTrie t x -> Tree (t, Maybe x)
instance (Test.QuickCheck.Arbitrary.Arbitrary t, Test.QuickCheck.Arbitrary.Arbitrary x) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.List.ListTrie t x)
instance Data.Traversable.Traversable (Data.Trie.List.ListTrie t)
instance Data.Foldable.Foldable (Data.Trie.List.ListTrie t)
instance GHC.Base.Functor (Data.Trie.List.ListTrie t)
instance (GHC.Classes.Eq t, GHC.Classes.Eq x) => GHC.Classes.Eq (Data.Trie.List.ListTrie t x)
instance (GHC.Show.Show t, GHC.Show.Show x) => GHC.Show.Show (Data.Trie.List.ListTrie t x)
instance GHC.Classes.Eq s => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s Data.Trie.List.ListTrie

module Data.Trie.Map
newtype MapStep c p a
MapStep :: Map p (Maybe a, Maybe (c p a)) -> MapStep c p a
[unMapStep] :: MapStep c p a -> Map p (Maybe a, Maybe (c p a))

-- | No insertion instance - requires children nodes to be a monoid. Use
--   <tt>Data.Trie.Map.insert</tt> instead.
insert :: (Ord p, Trie NonEmpty p c, Monoid (c p a)) => NonEmpty p -> a -> MapStep c p a -> MapStep c p a
empty :: MapStep c s a
singleton :: s -> a -> MapStep c s a
newtype MapTrie s a
MapTrie :: MapStep MapTrie s a -> MapTrie s a
[unMapTrie] :: MapTrie s a -> MapStep MapTrie s a
keys :: Ord s => MapTrie s a -> [NonEmpty s]
elems :: MapTrie s a -> [a]
subtrie :: Ord s => NonEmpty s -> MapTrie s a -> Maybe (MapTrie s a)
match :: Ord s => NonEmpty s -> MapTrie s a -> Maybe (NonEmpty s, a, [s])

-- | Returns a list of all the nodes along the path to the furthest point
--   in the query, in order of the path walked from the root to the
--   furthest point.
matches :: Ord s => NonEmpty s -> MapTrie s a -> [(NonEmpty s, a, [s])]
instance (GHC.Classes.Ord s, Test.QuickCheck.Arbitrary.Arbitrary s, Test.QuickCheck.Arbitrary.Arbitrary a) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.Map.MapTrie s a)
instance GHC.Classes.Ord s => GHC.Base.Monoid (Data.Trie.Map.MapTrie s a)
instance Data.Traversable.Traversable (Data.Trie.Map.MapTrie s)
instance Data.Foldable.Foldable (Data.Trie.Map.MapTrie s)
instance GHC.Base.Functor (Data.Trie.Map.MapTrie s)
instance (GHC.Classes.Ord s, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Trie.Map.MapTrie s a)
instance (GHC.Classes.Eq s, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Trie.Map.MapTrie s a)
instance (GHC.Show.Show s, GHC.Show.Show a) => GHC.Show.Show (Data.Trie.Map.MapTrie s a)
instance Data.Traversable.Traversable (c p) => Data.Traversable.Traversable (Data.Trie.Map.MapStep c p)
instance Data.Foldable.Foldable (c p) => Data.Foldable.Foldable (Data.Trie.Map.MapStep c p)
instance GHC.Base.Functor (c p) => GHC.Base.Functor (Data.Trie.Map.MapStep c p)
instance (GHC.Classes.Ord p, GHC.Classes.Ord a, GHC.Classes.Ord (c p a)) => GHC.Classes.Ord (Data.Trie.Map.MapStep c p a)
instance (GHC.Classes.Eq p, GHC.Classes.Eq a, GHC.Classes.Eq (c p a)) => GHC.Classes.Eq (Data.Trie.Map.MapStep c p a)
instance (GHC.Show.Show p, GHC.Show.Show a, GHC.Show.Show (c p a)) => GHC.Show.Show (Data.Trie.Map.MapStep c p a)
instance (Test.QuickCheck.Arbitrary.Arbitrary a, Test.QuickCheck.Arbitrary.Arbitrary p, Test.QuickCheck.Arbitrary.Arbitrary (c p a), GHC.Classes.Ord p) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Trie.Map.MapStep c p a)
instance (GHC.Classes.Ord p, Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty p c) => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty p (Data.Trie.Map.MapStep c)
instance (GHC.Classes.Ord s, GHC.Base.Monoid (c s a)) => GHC.Base.Monoid (Data.Trie.Map.MapStep c s a)
instance GHC.Classes.Ord s => Data.Trie.Class.Trie Data.List.NonEmpty.NonEmpty s Data.Trie.Map.MapTrie
instance GHC.Classes.Ord s => Data.Key.Lookup (Data.Trie.Map.MapTrie s)