Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell98 |
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.
Synopsis
- class Memoizable a where
- memoize :: (a -> v) -> a -> v
- memoize2 :: (Memoizable a, Memoizable b) => (a -> b -> v) -> a -> b -> v
- memoize3 :: (Memoizable a, Memoizable b, Memoizable c) => (a -> b -> c -> v) -> a -> b -> c -> v
- memoize4 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => (a -> b -> c -> d -> v) -> a -> b -> c -> d -> v
- memoize5 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e) => (a -> b -> c -> d -> e -> v) -> a -> b -> c -> d -> e -> v
- 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
- 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
- memoFix :: Memoizable a => ((a -> v) -> a -> v) -> a -> v
- memoFix2 :: (Memoizable a, Memoizable b) => ((a -> b -> v) -> a -> b -> v) -> a -> b -> v
- memoFix3 :: (Memoizable a, Memoizable b, Memoizable c) => ((a -> b -> c -> v) -> a -> b -> c -> v) -> a -> b -> c -> v
- memoFix4 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => ((a -> b -> c -> d -> v) -> a -> b -> c -> d -> v) -> a -> b -> c -> d -> v
- 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
- 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
- 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
- traceMemoize :: (Memoizable a, Show a) => (a -> b) -> a -> b
- memoizeFinite :: (Enum a, Bounded a) => (a -> v) -> a -> v
- deriveMemoizable :: Name -> Q [Dec]
- deriveMemoizableParams :: Name -> [Int] -> Q [Dec]
- deriveMemoize :: Name -> ExpQ
Memoization class
class Memoizable a where Source #
A memoization class. An instance
for some
type Memoizable
TT
means that that memoize
method can memoize for
parameters of type T
.
Instances
Operations
Higher-arity memoize
memoize2 :: (Memoizable a, Memoizable b) => (a -> b -> v) -> a -> b -> v Source #
Memoize a two argument function
memoize3 :: (Memoizable a, Memoizable b, Memoizable c) => (a -> b -> c -> v) -> a -> b -> c -> v Source #
Memoize a three argument function
memoize4 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => (a -> b -> c -> d -> v) -> a -> b -> c -> d -> v Source #
Memoize a four 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 Source #
Memoize a five 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 Source #
Memoize a six 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 Source #
Memoize a seven argument function
Memoizing open recursion
memoFix :: Memoizable a => ((a -> v) -> a -> v) -> a -> v Source #
Memoizes the least fixed point of a function. This is like
fix
, but it passes the fixed function a memoized
version of itself, so this memoizes using all recursive calls as well.
memoFix2 :: (Memoizable a, Memoizable b) => ((a -> b -> v) -> a -> b -> v) -> a -> b -> v Source #
Two argument version of memoFix
.
memoFix3 :: (Memoizable a, Memoizable b, Memoizable c) => ((a -> b -> c -> v) -> a -> b -> c -> v) -> a -> b -> c -> v Source #
Three argument version of memoFix
.
memoFix4 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => ((a -> b -> c -> d -> v) -> a -> b -> c -> d -> v) -> a -> b -> c -> d -> v Source #
Four argument version of memoFix
.
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 Source #
Five argument version of memoFix
.
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 Source #
Six argument version of memoFix
.
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 Source #
Seven argument version of memoFix
.
Tracing memoization
traceMemoize :: (Memoizable a, Show a) => (a -> b) -> a -> b Source #
For making instances for finite types
memoizeFinite :: (Enum a, Bounded a) => (a -> v) -> a -> v Source #
Can be used to memoize over any "finite" type satisfying
Enum
and Bounded
. This builds a binary search tree, treating
the memoized type as isomorphic to a range of Int
, so it will be
only as efficient as toEnum
, fromEnum
, succ
, and pred
.
This can be used to make instances for finite types. For example, the
instances for Int
and Char
are declared as:
instance Memoizable Int where memoize = memoizeFinite instance Memoizable Char where memoize = memoizeFinite
Deriving Memoizable
deriveMemoizable :: Name -> Q [Dec] Source #
To derive Memoizable
instances for the given data types.
In the simplest usage, to derive Memoizable
for an algebraic
datatype named T
, write:
deriveMemoizable ''T
This assumes that all the type parameters of T
that are not
annotated with a kind other than *
should be listed as requiring
Memoizable
instances in the instance context. For example, given
a data type declared as
data T a (b :: * -> *) c = ...
the generated instance will look like
instance (Memoizable
a,Memoizable
c) =>Memoizable
(T a b c) where ...
For more precise control over the context, use
deriveMemoizableParams
.
N.B.: The TemplateHaskell
language extension must be enabled to use
this function.
deriveMemoizableParams :: Name -> [Int] -> Q [Dec] Source #
Like deriveMemoizable
but takes a second argument, which is a list
of Int
s to specify which type parameters of the type should be
mentioned in the context. For example, given the same definition for
T
as above, we can write
deriveMemoizableParams ''T [3]
to leave the first parameter of T
out of the context and show
only the third, yielding the instance
instanceMemoizable
c =>Memoizable
(T a b c) where ...
N.B.: The TemplateHaskell
language extension must be enabled to use
this function.
deriveMemoize :: Name -> ExpQ Source #
In cases where neither deriveMemoizable
nor
deriveMemoizableParams
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 memoize
. For example,
suppose that a data type T
is defined as:
data T a b = T (a -> Bool) b
For T a b
to be memoizable, a -> Bool
must be, and based on the
instance for (->)
, this means that a
must satisfy
Bounded
and Enum
, so deriveMemoizable
cannot build the right
context for the Memoizable
instance. Instead, one can write:
instance (Eq
a,Enum
a,Bounded
a,Memoizable
b) =>Memoizable
(T a b) where memoize = $(deriveMemoize ''T)