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


-- | A map, where the keys may be complex structured data.
--   
--   This type implements maps where the keys are themselves complex
--   structured data. For example, the keys may be the abstract syntax
--   trees for a programming language. The map is implemented as a trie, so
--   common parts of the keys will be shared in the representation. The
--   library provides a generic implementation of the data structure, so
--   values of types that have support for <a>Generic</a> may be
--   automatically used as keys in the map.
@package generic-trie
@version 0.2


-- | This module implements an interface for working with "tries". A key in
--   the trie represents a distinct path through the trie. This can provide
--   benefits when using very large and possibly very similar keys where
--   comparing for order can become expensive, and storing the various keys
--   could be inefficient.
--   
--   For primitive types like <a>Int</a>, this library will select
--   efficient implementations automatically.
--   
--   All methods of <a>TrieKey</a> can be derived automatically using a
--   <a>Generic</a> instance.
--   
--   <pre>
--   data Demo = DemoC1 <a>Int</a> | DemoC2 <a>Int</a> <a>Char</a>  deriving <a>Generic</a>
--   
--   instance <a>TrieKey</a> Demo
--   </pre>
module Data.GenericTrie

-- | Effectively an associated datatype of tries indexable by keys of type
--   <tt>k</tt>. By using a separate newtype wrapper around the associated
--   type synonym we're able to use the same <a>MkTrie</a> constructor for
--   all of the generic implementations while still getting the injectivity
--   of a new type.
newtype Trie k a
MkTrie :: (TrieRep k a) -> Trie k a

-- | Alter the values of a trie. The function will take the value stored as
--   the given key if one exists and should return a value to insert at
--   that location or Nothing to delete from that location.
alter :: TrieKey k => k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a

-- | Returns <a>True</a> when the <a>Trie</a> has a value stored at the
--   given key.
member :: TrieKey k => k -> Trie k a -> Bool

-- | Returns <a>False</a> when the <a>Trie</a> has a value stored at the
--   given key.
notMember :: TrieKey k => k -> Trie k a -> Bool

-- | Construct a trie from a list of key/value pairs
fromList :: TrieKey k => [(k, v)] -> Trie k v

-- | Transform <a>Trie</a> to an association list.
toList :: TrieKey k => Trie k a -> [(k, a)]
mapMaybe :: TrieKey k => (a -> Maybe b) -> Trie k a -> Trie k b
union :: TrieKey k => Trie k a -> Trie k a -> Trie k a
unionWith :: TrieKey k => (a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWithKey :: TrieKey k => (k -> a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
intersection :: TrieKey k => Trie k a -> Trie k b -> Trie k a
intersectionWith :: TrieKey k => (a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
intersectionWithKey :: TrieKey k => (k -> a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
difference :: TrieKey k => Trie k a -> Trie k b -> Trie k a
differenceWith :: TrieKey k => (a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
differenceWithKey :: TrieKey k => (k -> a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a

-- | Keys that support prefix-trie map operations.
--   
--   All operations can be automatically derived from a <a>Generic</a>
--   instance.
class TrieKey k where type family TrieRep k :: * -> * type instance TrieRep k = TrieRepDefault k empty = genericEmpty singleton = genericSingleton trieNull = genericTrieNull lookup = genericLookup insert = genericInsert delete = genericDelete trieMap = genericTrieMap trieTraverse = genericTrieTraverse trieShowsPrec = genericTrieShowsPrec mapMaybeWithKey = genericMapMaybeWithKey foldWithKey = genericFoldWithKey traverseWithKey = genericTraverseWithKey mergeWithKey = genericMergeWithKey
empty :: TrieKey k => Trie k a
trieNull :: TrieKey k => Trie k a -> Bool
lookup :: TrieKey k => k -> Trie k a -> Maybe a
insert :: TrieKey k => k -> a -> Trie k a -> Trie k a
delete :: TrieKey k => k -> Trie k a -> Trie k a
singleton :: TrieKey k => k -> a -> Trie k a
trieMap :: TrieKey k => (a -> b) -> Trie k a -> Trie k b
trieTraverse :: (TrieKey k, Applicative f) => (a -> f b) -> Trie k a -> f (Trie k b)
trieShowsPrec :: (TrieKey k, Show a) => Int -> Trie k a -> ShowS
mapMaybeWithKey :: TrieKey k => (k -> a -> Maybe b) -> Trie k a -> Trie k b
foldWithKey :: TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
traverseWithKey :: (TrieKey k, Applicative f) => (k -> a -> f b) -> Trie k a -> f (Trie k b)
mergeWithKey :: TrieKey k => (k -> a -> b -> Maybe c) -> (Trie k a -> Trie k c) -> (Trie k b -> Trie k c) -> Trie k a -> Trie k b -> Trie k c
newtype OrdKey k
OrdKey :: k -> OrdKey k
getOrdKey :: OrdKey k -> k

-- | Generic implementation of <a>trieNull</a>. This is the default
--   implementation.
genericTrieNull :: TrieRep k ~ TrieRepDefault k => Trie k a -> Bool

-- | Generic implementation of <a>trieMap</a>. This is the default
--   implementation.
genericTrieMap :: (GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k) => (a -> b) -> Trie k a -> Trie k b

-- | Generic implementation of <a>trieTraverse</a>. This is the default
--   implementation.
genericTrieTraverse :: (GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k, Applicative f) => (a -> f b) -> Trie k a -> f (Trie k b)

-- | Generic implementation of <a>trieShowsPrec</a>. This is the default
--   implementation.
genericTrieShowsPrec :: (Show a, GTrieKeyShow (Rep k), TrieRep k ~ TrieRepDefault k) => Int -> Trie k a -> ShowS

-- | Generic implementation of <a>insert</a>. This is the default
--   implementation.
genericInsert :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> a -> Trie k a -> Trie k a

-- | Generic implementation of <a>lookup</a>. This is the default
--   implementation.
genericLookup :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> Trie k a -> Maybe a

-- | Generic implementation of <a>delete</a>. This is the default
--   implementation.
genericDelete :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> Trie k a -> Trie k a

-- | Generic implementation of <a>mapMaybe</a>. This is the default
--   implementation.
genericMapMaybeWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => (k -> a -> Maybe b) -> Trie k a -> Trie k b

-- | Generic implementation of <a>singleton</a>. This is the default
--   implementation.
genericSingleton :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> a -> Trie k a

-- | Generic implementation of <a>empty</a>. This is the default
--   implementation.
genericEmpty :: TrieRep k ~ TrieRepDefault k => Trie k a

-- | Generic implementation of <a>foldWithKey</a>. This is the default
--   implementation.
genericFoldWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => (k -> a -> r -> r) -> r -> Trie k a -> r

-- | Generic implementation of <a>traverseWithKey</a>. This is the default
--   implementation.
genericTraverseWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k, Applicative f) => (k -> a -> f b) -> Trie k a -> f (Trie k b)

-- | The default implementation of a <a>TrieRep</a> is <a>GTrie</a> wrapped
--   in a <a>Maybe</a>. This wrapping is due to the <a>GTrie</a> being a
--   non-empty trie allowing all the of the "emptiness" to be represented
--   at the top level for any given generically implemented key.
type TrieRepDefault k = Compose Maybe (GTrie (Rep k))

-- | TrieKey operations on Generic representations used to provide the
--   default implementations of tries.
class GTrieKey f
gtrieLookup :: GTrieKey f => f p -> GTrie f a -> Maybe a
gtrieInsert :: GTrieKey f => f p -> a -> GTrie f a -> GTrie f a
gtrieSingleton :: GTrieKey f => f p -> a -> GTrie f a
gtrieDelete :: GTrieKey f => f p -> GTrie f a -> Maybe (GTrie f a)
gtrieMap :: GTrieKey f => (a -> b) -> GTrie f a -> GTrie f b
gtrieTraverse :: (GTrieKey f, Applicative m) => (a -> m b) -> GTrie f a -> m (GTrie f b)
gmapMaybeWithKey :: GTrieKey f => (f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
gfoldWithKey :: GTrieKey f => (f p -> a -> r -> r) -> r -> GTrie f a -> r
gtraverseWithKey :: (GTrieKey f, Applicative m) => (f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
gmergeWithKey :: GTrieKey f => (f p -> a -> b -> Maybe c) -> (GTrie f a -> Maybe (GTrie f c)) -> (GTrie f b -> Maybe (GTrie f c)) -> GTrie f a -> GTrie f b -> Maybe (GTrie f c)

-- | Mapping of generic representation of keys to trie structures.
instance Read k => Read (OrdKey k)
instance Show k => Show (OrdKey k)
instance Eq k => Eq (OrdKey k)
instance Ord k => Ord (OrdKey k)
instance TrieKey k => Traversable (Trie k)
instance TrieKey k => Foldable (Trie k)
instance TrieKey k => Functor (Trie k)
instance (Show a, GTrieKeyShow f) => Show (GTrie f a)
instance (Show a, TrieKey k) => Show (Trie k a)
instance GTrieKeyShow V1
instance GTrieKey V1
instance GTrieKeyShow U1
instance GTrieKey U1
instance (GTrieKeyShow f, GTrieKeyShow g) => GTrieKeyShow (f :+: g)
instance (GTrieKey f, GTrieKey g) => GTrieKey (f :+: g)
instance (GTrieKeyShow f, GTrieKeyShow g) => GTrieKeyShow (f :*: g)
instance (GTrieKey f, GTrieKey g) => GTrieKey (f :*: g)
instance TrieKey k => GTrieKeyShow (K1 i k)
instance TrieKey k => GTrieKey (K1 i k)
instance GTrieKeyShow f => GTrieKeyShow (M1 S s f)
instance (Constructor c, GTrieKeyShow f) => GTrieKeyShow (M1 C c f)
instance GTrieKeyShow f => GTrieKeyShow (M1 D d f)
instance GTrieKey f => GTrieKey (M1 i c f)
instance GTrieKey f => Functor (GTrie f)
instance TrieKey k => TrieKey [k]
instance (TrieKey a, TrieKey b, TrieKey c) => TrieKey (a, b, c)
instance (TrieKey a, TrieKey b) => TrieKey (a, b)
instance (TrieKey a, TrieKey b) => TrieKey (Either a b)
instance TrieKey k => TrieKey (Maybe k)
instance TrieKey Bool
instance TrieKey ()
instance (Show k, Ord k) => TrieKey (OrdKey k)
instance TrieKey Char
instance TrieKey Integer
instance TrieKey Int