-- 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.
--   
--   Project wiki page: <a>http://haskell.org/haskellwiki/MemoTrie</a>
--   
--   © 2008-2012 by Conal Elliott; BSD3 license.
@package MemoTrie
@version 0.6.2


-- | Trie-based memoizer
--   
--   Adapted from sjanssen's paste: "a lazy trie"
--   <a>http://hpaste.org/3839</a>, which I think is based on Ralf Hinze's
--   paper "Memo Functions, Polytypically!".
module Data.MemoTrie

-- | Mapping from all elements of <tt>a</tt> to the results of some
--   function
class HasTrie a where data family (:->:) a :: * -> *
trie :: HasTrie a => (a -> b) -> (a :->: b)
untrie :: HasTrie a => (a :->: b) -> (a -> b)
enumerate :: HasTrie a => (a :->: b) -> [(a, b)]

-- | 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)

-- | 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))
instance HasTrie a => Monad ((:->:) a)
instance HasTrie a => Applicative ((:->:) a)
instance HasTrie a => Functor ((:->:) a)
instance (HasTrie a, Monoid b) => Monoid (a :->: b)
instance HasTrie Integer
instance HasTrie Int64
instance HasTrie Int32
instance HasTrie Int16
instance HasTrie Int8
instance HasTrie Int
instance HasTrie Char
instance HasTrie Word64
instance HasTrie Word32
instance HasTrie Word16
instance HasTrie Word8
instance HasTrie Word
instance HasTrie x => HasTrie [x]
instance (HasTrie a, HasTrie b, HasTrie c) => HasTrie (a, b, c)
instance (HasTrie a, HasTrie b) => HasTrie (a, b)
instance (HasTrie a, HasTrie b) => HasTrie (Either a b)
instance HasTrie Bool
instance HasTrie ()
instance HasTrie Void
instance (HasTrie a, Show a, Show b) => Show (a :->: b)
instance (HasTrie a, Eq b) => Eq (a :->: b)
