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


-- | A memoization library
--   
--   This library provides a type class <a>Memoizable</a> for memoizing
--   functions, along with instances for a variety of argument types. It
--   includes a Template Haskell function for deriving <a>Memoizable</a>
--   instances for arbitrary algebraic datatypes.
--   
--   The library constructs pure memo caches without the use of
--   <a>unsafePerformIO</a>. This technique relies on implementation
--   assumptions that, while not guaranteed by the semantics of Haskell,
--   appear to be true.
@package memoize
@version 0.1


-- | A function memoization library.
--   
--   This includes a class for memoizable argument types and a Template
--   Haskell expander for deriving instances of the class.
--   
--   Note that most memoization in this style relies on assumptions about
--   the implementation of non-strictness (as laziness) that are not
--   guaranteed by the semantics. However, it appears to work.
module Data.Function.Memoize

-- | A memoization class. An instance <tt><a>Memoizable</a> T</tt> for some
--   type <tt>T</tt> means that that <a>memoize</a> method can memoize for
--   parameters of type <tt>T</tt>.
class Memoizable a
memoize :: Memoizable a => (a -> v) -> a -> v

-- | Memoize a two argument function
memoize2 :: (Memoizable a, Memoizable b) => (a -> b -> v) -> a -> b -> v

-- | Memoize a three argument function
memoize3 :: (Memoizable a, Memoizable b, Memoizable c) => (a -> b -> c -> v) -> a -> b -> c -> v

-- | Memoize a four argument function
memoize4 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => (a -> b -> c -> d -> v) -> a -> b -> c -> d -> v

-- | Memoize a five argument function
memoize5 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e) => (a -> b -> c -> d -> e -> v) -> a -> b -> c -> d -> e -> v

-- | Memoize a six argument function
memoize6 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f) => (a -> b -> c -> d -> e -> f -> v) -> a -> b -> c -> d -> e -> f -> v

-- | Memoize a seven argument function
memoize7 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g) => (a -> b -> c -> d -> e -> f -> g -> v) -> a -> b -> c -> d -> e -> f -> g -> v

-- | Memoizes the least fixed point of a function. This is like
--   <tt>Data.Function.fix</tt>, but it passes the fixed function a
--   memoized version of itself, so this memoizes using all recursive calls
--   as well.
memoFix :: Memoizable a => ((a -> v) -> a -> v) -> a -> v

-- | Two argument version of <a>memoFix</a>.
memoFix2 :: (Memoizable a, Memoizable b) => ((a -> b -> v) -> a -> b -> v) -> a -> b -> v

-- | Three argument version of <a>memoFix</a>.
memoFix3 :: (Memoizable a, Memoizable b, Memoizable c) => ((a -> b -> c -> v) -> a -> b -> c -> v) -> a -> b -> c -> v

-- | Four argument version of <a>memoFix</a>.
memoFix4 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => ((a -> b -> c -> d -> v) -> (a -> b -> c -> d -> v)) -> a -> b -> c -> d -> v

-- | Five argument version of <a>memoFix</a>.
memoFix5 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e) => ((a -> b -> c -> d -> e -> v) -> (a -> b -> c -> d -> e -> v)) -> a -> b -> c -> d -> e -> v

-- | Six argument version of <a>memoFix</a>.
memoFix6 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f) => ((a -> b -> c -> d -> e -> f -> v) -> (a -> b -> c -> d -> e -> f -> v)) -> a -> b -> c -> d -> e -> f -> v

-- | Seven argument version of <a>memoFix</a>.
memoFix7 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g) => ((a -> b -> c -> d -> e -> f -> g -> v) -> (a -> b -> c -> d -> e -> f -> g -> v)) -> a -> b -> c -> d -> e -> f -> g -> v

-- | Give a one-argument function whose argument satisfies <a>Show</a>,
--   this memoizes the function such that the argument is shown (using
--   <a>trace</a>) only when the function has to be applied, as opposed to
--   when the answer is available in the memo cache.
traceMemoize :: (Memoizable a, Show a) => (a -> b) -> a -> b

-- | Can be used to memoize over any <a>finite</a> type satisfying
--   <a>Enum</a> and <a>Bounded</a>. This builds a binary search tree,
--   treating the memoized type as isomorphic to a range of <a>Int</a>, so
--   it will be only as efficient as <a>toEnum</a>, <a>fromEnum</a>,
--   <a>succ</a>, and <a>pred</a>.
--   
--   This can be used to make instances for finite types. For example, the
--   instances for <a>Int</a> and <a>Char</a> are declared as:
--   
--   <pre>
--   instance Memoizable Int where memoize = memoizeFinite
--   instance Memoizable Char where memoize = memoizeFinite
--   </pre>
memoizeFinite :: (Enum a, Bounded a) => (a -> v) -> a -> v

-- | To derive <a>Memoizable</a> instances for the given data types. In the
--   simplest usage, to derive <a>Memoizable</a> for an algebraic datatype
--   named <tt>T</tt>, write:
--   
--   <pre>
--   deriveMemoizable ''T
--   </pre>
--   
--   This assumes that all the type parameters of <tt>T</tt> that are not
--   annotated with a kind other than <tt>*</tt> should be listed as
--   requiring <a>Memoizable</a> instances in the instance context. For
--   example, given a data type declared as
--   
--   <pre>
--   data T a (b :: * -&gt; *) c = ...
--   </pre>
--   
--   the generated instance will look like
--   
--   <pre>
--   instance (<a>Memoizable</a> a, <a>Memoizable</a> c) =&gt;
--            <a>Memoizable</a> (T a b c) where ...
--   </pre>
--   
--   For more precise control over the context, use
--   <a>deriveMemoizableParams</a>.
--   
--   N.B.: The <tt>TemplateHaskell</tt> language extension must be enabled
--   to use this function.
deriveMemoizable :: Name -> Q [Dec]

-- | Like <a>deriveMemoizable</a> but takes a second argument, which is a
--   list of <a>Int</a>s to specify which type parameters of the type
--   should be mentioned in the context. For example, given the same
--   definition for <tt>T</tt> as above, we can write
--   
--   <pre>
--   deriveMemoizableParams ''T [3]
--   </pre>
--   
--   to leave the first parameter of <tt>T</tt> out of the context and show
--   only the third, yielding the instance
--   
--   <pre>
--   instance <a>Memoizable</a> c =&gt; <a>Memoizable</a> (T a b c) where ...
--   </pre>
--   
--   N.B.: The <tt>TemplateHaskell</tt> language extension must be enabled
--   to use this function.
deriveMemoizableParams :: Name -> [Int] -> Q [Dec]

-- | In cases where neither <a>deriveMemoizable</a> nor
--   <a>deriveMemoizableParams</a> can figure out the right context for an
--   instance declaration, one can declare the instance manually and use
--   this function to derive the method body for <a>memoize</a>. For
--   example, suppose that a data type <tt>T</tt> is defined as:
--   
--   <pre>
--   data T a b = T (a -&gt; Bool) b
--   </pre>
--   
--   For <tt>T a b</tt> to be memoizable, <tt>a -&gt; Bool</tt> must be,
--   and based on the instance for '(-&gt;)', this means that <tt>a</tt>
--   must satisfy <a>Bounded</a> and <a>Enum</a>, so
--   <a>deriveMemoizable</a> cannot build the right context for the
--   <a>Memoizable</a> instance. Instead, one can write:
--   
--   <pre>
--   instance (<a>Enum</a> a, <a>Bounded</a> a, <a>Memoizable</a> b) =&gt;
--            <a>Memoizable</a> (T a b) where
--     memoize = $(deriveMemoize ''T)
--   </pre>
deriveMemoize :: Name -> ExpQ
instance Functor BinaryTreeCache
instance Functor IntegerCache
instance Eq a => Eq (Finite a)
instance Bounded a => Bounded (Finite a)
instance Enum a => Enum (Finite a)
instance (Eq a, Bounded a, Enum a, Memoizable b) => Memoizable (a -> b)
instance Memoizable Char
instance Memoizable Int
instance (Bounded a, Enum a) => Memoizable (Finite a)
instance Memoizable Integer
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g, Memoizable h, Memoizable i, Memoizable j, Memoizable k, Memoizable l) => Memoizable (a, b, c, d, e, f, g, h, i, j, k, l)
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g, Memoizable h, Memoizable i, Memoizable j, Memoizable k) => Memoizable (a, b, c, d, e, f, g, h, i, j, k)
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g, Memoizable h, Memoizable i, Memoizable j) => Memoizable (a, b, c, d, e, f, g, h, i, j)
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g, Memoizable h, Memoizable i) => Memoizable (a, b, c, d, e, f, g, h, i)
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g, Memoizable h) => Memoizable (a, b, c, d, e, f, g, h)
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g) => Memoizable (a, b, c, d, e, f, g)
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f) => Memoizable (a, b, c, d, e, f)
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e) => Memoizable (a, b, c, d, e)
instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => Memoizable (a, b, c, d)
instance (Memoizable a, Memoizable b, Memoizable c) => Memoizable (a, b, c)
instance (Memoizable a, Memoizable b) => Memoizable (a, b)
instance Memoizable a => Memoizable [a]
instance (Memoizable a, Memoizable b) => Memoizable (Either a b)
instance Memoizable a => Memoizable (Maybe a)
instance Memoizable Ordering
instance Memoizable Bool
instance Memoizable ()