-- 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: http://haskell.org/haskellwiki/MemoTrie
--   
--   Ç 2008-2019 by Conal Elliott; BSD3 license.
@package MemoTrie
@version 0.6.11

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

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

-- | 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 (:: a) is always the
--   same.
enumerate :: HasTrie a => (a :->: b) -> [(a, b)]
infixr 0 :->:

-- | Representation of trie with domain type a
data family a :->: :: Type -> Type
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

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

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

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

-- | the data type in a regular form. "unlifted" generic
--   representation. (i.e. is a unary type constructor).
type Reg a = Rep a ()

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