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


-- | Trie-based memo functions
--   
--   MemoTrie provides a basis for memoized functions over some domains,
--   using tries. It's based on ideas from Ralf Hinze and code from Spencer
--   Janssen. Generic support thanks to Sam Boosalis.
--   
--   Project wiki page: <a>http://haskell.org/haskellwiki/MemoTrie</a>
--   
--   Ç 2008-2019 by Conal Elliott; BSD3 license.
@package MemoTrie
@version 0.6.11


-- | Trie-based memoizer
--   
--   Adapted from sjanssen's paste: <a>"a lazy trie"</a>, which I think is
--   based on Ralf Hinze's paper "Memo Functions, Polytypically!".
--   
--   You can automatically derive generic instances. for example:
--   
--   <pre>
--   {-# LANGUAGE <a>DeriveGeneric</a>, TypeOperators, TypeFamilies #-}
--   import Data.MemoTrie
--   import GHC.Generics (Generic) 
--   
--   data Color = RGB Int Int Int
--              | NamedColor String 
--    deriving (<a>Generic</a>) 
--   
--   instance HasTrie Color where
--     newtype (Color :-&gt;: b) = ColorTrie { unColorTrie :: <a>Reg</a> Color :-&gt;: b } 
--     trie = <a>trieGeneric</a> ColorTrie 
--     untrie = <a>untrieGeneric</a> unColorTrie
--     enumerate = <a>enumerateGeneric</a> unColorTrie
--   </pre>
--   
--   see <tt>examples/Generic.hs</tt>, which can be run with:
--   
--   <pre>
--   cabal configure -fexamples &amp;&amp; cabal run generic
--   </pre>
module Data.MemoTrie

-- | Mapping from all elements of <tt>a</tt> to the results of some
--   function
class HasTrie a where {
    
    -- | Representation of trie with domain type <tt>a</tt>
    data (:->:) a :: * -> *;
}

-- | Create the trie for the entire domain of a function
trie :: HasTrie a => (a -> b) -> a :->: b

-- | Convert a trie to a function, i.e., access a field of the trie
untrie :: HasTrie a => (a :->: b) -> a -> b

-- | List the trie elements. Order of keys (<tt>:: a</tt>) is always the
--   same.
enumerate :: HasTrie a => (a :->: b) -> [(a, b)]
infixr 0 :->:

-- | Domain elements of a trie
domain :: HasTrie a => [a]

-- | Identity trie
idTrie :: HasTrie a => a :->: a

-- | Trie composition
(@.@) :: (HasTrie a, HasTrie b) => (b :->: c) -> (a :->: b) -> a :->: c
infixr 9 @.@

-- | Trie-based function memoizer
memo :: HasTrie t => (t -> a) -> t -> a

-- | Memoize a binary function, on its first argument and then on its
--   second. Take care to exploit any partial evaluation.
memo2 :: (HasTrie s, HasTrie t) => (s -> t -> a) -> s -> t -> a

-- | Memoize a ternary function on successive arguments. Take care to
--   exploit any partial evaluation.
memo3 :: (HasTrie r, HasTrie s, HasTrie t) => (r -> s -> t -> a) -> r -> s -> t -> a

-- | Lift a memoizer to work with one more argument.
mup :: HasTrie t => (b -> c) -> (t -> b) -> t -> c

-- | Apply a unary function inside of a trie
inTrie :: (HasTrie a, HasTrie c) => ((a -> b) -> c -> d) -> (a :->: b) -> c :->: d

-- | Apply a binary function inside of a trie
inTrie2 :: (HasTrie a, HasTrie c, HasTrie e) => ((a -> b) -> (c -> d) -> e -> f) -> (a :->: b) -> (c :->: d) -> e :->: f

-- | Apply a ternary function inside of a trie
inTrie3 :: (HasTrie a, HasTrie c, HasTrie e, HasTrie g) => ((a -> b) -> (c -> d) -> (e -> f) -> g -> h) -> (a :->: b) -> (c :->: d) -> (e :->: f) -> g :->: h

-- | <a>Generic</a>-friendly default for <a>trie</a>
trieGeneric :: (Generic a, HasTrie (Reg a)) => ((Reg a :->: b) -> a :->: b) -> (a -> b) -> a :->: b

-- | <a>Generic</a>-friendly default for <a>untrie</a>
untrieGeneric :: (Generic a, HasTrie (Reg a)) => ((a :->: b) -> Reg a :->: b) -> (a :->: b) -> a -> b

-- | <a>Generic</a>-friendly default for <a>enumerate</a>
enumerateGeneric :: (Generic a, HasTrie (Reg a)) => ((a :->: b) -> Reg a :->: b) -> (a :->: b) -> [(a, b)]

-- | the data type in a <b>reg</b>ular form. "unlifted" generic
--   representation. (i.e. is a unary type constructor).
type Reg a = Rep a ()

-- | Memoizing recursion. Use like <a>fix</a>.
memoFix :: HasTrie a => ((a -> b) -> a -> b) -> a -> b
instance (Data.MemoTrie.HasTrie a, GHC.Classes.Eq b) => GHC.Classes.Eq (a Data.MemoTrie.:->: b)
instance (Data.MemoTrie.HasTrie a, GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (a Data.MemoTrie.:->: b)
instance Data.MemoTrie.HasTrie GHC.Base.Void
instance Control.Newtype.Generics.Newtype (GHC.Base.Void Data.MemoTrie.:->: a)
instance Data.MemoTrie.HasTrie ()
instance Control.Newtype.Generics.Newtype (() Data.MemoTrie.:->: a)
instance Data.MemoTrie.HasTrie GHC.Types.Bool
instance Control.Newtype.Generics.Newtype (GHC.Types.Bool Data.MemoTrie.:->: a)
instance Data.MemoTrie.HasTrie a => Data.MemoTrie.HasTrie (GHC.Maybe.Maybe a)
instance Control.Newtype.Generics.Newtype (GHC.Maybe.Maybe a Data.MemoTrie.:->: x)
instance (Data.MemoTrie.HasTrie a, Data.MemoTrie.HasTrie b) => Data.MemoTrie.HasTrie (Data.Either.Either a b)
instance Control.Newtype.Generics.Newtype (Data.Either.Either a b Data.MemoTrie.:->: x)
instance (Data.MemoTrie.HasTrie a, Data.MemoTrie.HasTrie b) => Data.MemoTrie.HasTrie (a, b)
instance Control.Newtype.Generics.Newtype ((a, b) Data.MemoTrie.:->: x)
instance (Data.MemoTrie.HasTrie a, Data.MemoTrie.HasTrie b, Data.MemoTrie.HasTrie c) => Data.MemoTrie.HasTrie (a, b, c)
instance Data.MemoTrie.HasTrie x => Data.MemoTrie.HasTrie [x]
instance Data.MemoTrie.HasTrie GHC.Types.Word
instance Data.MemoTrie.HasTrie GHC.Word.Word8
instance Data.MemoTrie.HasTrie GHC.Word.Word16
instance Data.MemoTrie.HasTrie GHC.Word.Word32
instance Data.MemoTrie.HasTrie GHC.Word.Word64
instance Data.MemoTrie.HasTrie GHC.Types.Char
instance Data.MemoTrie.HasTrie GHC.Types.Int
instance Data.MemoTrie.HasTrie GHC.Int.Int8
instance Data.MemoTrie.HasTrie GHC.Int.Int16
instance Data.MemoTrie.HasTrie GHC.Int.Int32
instance Data.MemoTrie.HasTrie GHC.Int.Int64
instance Data.MemoTrie.HasTrie GHC.Num.Integer.Integer
instance (Data.MemoTrie.HasTrie a, GHC.Base.Monoid b) => GHC.Base.Monoid (a Data.MemoTrie.:->: b)
instance (Data.MemoTrie.HasTrie a, GHC.Base.Semigroup b) => GHC.Base.Semigroup (a Data.MemoTrie.:->: b)
instance Data.MemoTrie.HasTrie a => GHC.Base.Functor ((Data.MemoTrie.:->:) a)
instance Data.MemoTrie.HasTrie a => GHC.Base.Applicative ((Data.MemoTrie.:->:) a)
instance Data.MemoTrie.HasTrie a => GHC.Base.Monad ((Data.MemoTrie.:->:) a)
instance Data.MemoTrie.HasTrie (GHC.Generics.V1 x)
instance Data.MemoTrie.HasTrie (GHC.Generics.U1 x)
instance (Data.MemoTrie.HasTrie (f x), Data.MemoTrie.HasTrie (g x)) => Data.MemoTrie.HasTrie ((GHC.Generics.:+:) f g x)
instance (Data.MemoTrie.HasTrie (f x), Data.MemoTrie.HasTrie (g x)) => Data.MemoTrie.HasTrie ((GHC.Generics.:*:) f g x)
instance Data.MemoTrie.HasTrie a => Data.MemoTrie.HasTrie (GHC.Generics.K1 i a x)
instance Data.MemoTrie.HasTrie (f x) => Data.MemoTrie.HasTrie (GHC.Generics.M1 i t f x)
