| Copyright | © 2018 Andy Morris |
|---|---|
| License | BSD-3-Clause |
| Maintainer | hello@andy-morris.xyz |
| Stability | experimental |
| Portability | TODO |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.HashCons.Memo
Description
Memoisation, using hash-consing as a way to identify arguments.
- class (Eq (Key k), Hashable (Key k)) => MemoArg k where
- type Key k :: Type
- type CanFinalize k :: Bool
- uncheckedMemo :: MemoArg a => (a -> b) -> a -> b
- memo :: (MemoArg a, CanFinalize a ~ True) => (a -> b) -> a -> b
- memo2 :: (MemoArg a, MemoArg b, CanFinalize a ~ True) => (a -> b -> c) -> a -> b -> c
- memo3 :: (MemoArg a, MemoArg b, MemoArg c, CanFinalize a ~ True) => (a -> b -> c -> d) -> a -> b -> c -> d
- memo4 :: (MemoArg a, MemoArg b, MemoArg c, MemoArg d, CanFinalize a ~ True) => (a -> b -> c -> d -> e) -> a -> b -> c -> d -> e
- uncheckedMemo2 :: (MemoArg a, MemoArg b) => (a -> b -> c) -> a -> b -> c
- uncheckedMemo3 :: (MemoArg a, MemoArg b, MemoArg c) => (a -> b -> c -> d) -> a -> b -> c -> d
- uncheckedMemo4 :: (MemoArg a, MemoArg b, MemoArg c, MemoArg d) => (a -> b -> c -> d -> e) -> a -> b -> c -> d -> e
Memo-suitable arguments
class (Eq (Key k), Hashable (Key k)) => MemoArg k where Source #
Types which can be arguments to a memo function. An empty instance assumes that a type is its own key, and can't run finalizers. The latter is the case for ordinary Haskell datatypes.
(TODO: add instances for everything in base)
Associated Types
A key which uniquely identifies a value. Defaults to the value itself. Otherwise, it should be something with fast equality and hashing, and must really be a unique identifier.
type CanFinalize k :: Bool Source #
Whether k can reliably run finalizers. (Most datatypes can't; see the
documentation for Weak for details.)
Methods
Extract the key. Defaults to the identity function for where
Key k ~ k
key :: Key k ~ k => k -> Key k Source #
Extract the key. Defaults to the identity function for where
Key k ~ k
tryAddFinalizer :: k -> Finalizer -> IO () Source #
Add a finalizer, if possible; otherwise, do nothing. Defaults to
doing nothing, for when CanFinalize k ~ 'False
Instances
Memoising functions
uncheckedMemo :: MemoArg a => (a -> b) -> a -> b Source #
Memoise a function, without checking that the memo table can be pruned. If it can't, then it will continue to grow throughout the program's run.
memo :: (MemoArg a, CanFinalize a ~ True) => (a -> b) -> a -> b Source #
Memoise a function, ensuring that the memo table can be pruned.
Nested memoisation
It is possible to memoise a multiple-argument function by nesting calls to
memo or uncheckedMemo, like so:
foo :: HC Beep -> HC Boop -> HC Bing -> HC Blah memoFoo :: HC Beep -> HC Boop -> HC Bing -> HC Blah memoFoo = memo $ \x -> memo $ \y -> memo $ foo x y
The functions memo2 to memo4 do this, with the first use being (checked)
memo and the other(s) being uncheckedMemo.
The user can use this pattern to write variations of a higher arity, or to check whichever arguments are desired.
Recommendations
- If possible, the first (or only) argument to a memoised function should be
able to run finalisers (e.g.,
HC): if a call touncheckedMemois nested inside a use ofmemo, then whole tables will be dropped by the outermemo's finalizers when no longer needed, even though they might not shrink before this time. Therefore, an outermostmemoensures that the memory usage is kept in check. - If the least-long-lived arguments come first, then the pruning will be more effective.
memo2 :: (MemoArg a, MemoArg b, CanFinalize a ~ True) => (a -> b -> c) -> a -> b -> c Source #
Memoise a binary function, checking that the outer table can be pruned.
memo3 :: (MemoArg a, MemoArg b, MemoArg c, CanFinalize a ~ True) => (a -> b -> c -> d) -> a -> b -> c -> d Source #
Memoise a ternary function, checking that the outermost table can be pruned.
memo4 :: (MemoArg a, MemoArg b, MemoArg c, MemoArg d, CanFinalize a ~ True) => (a -> b -> c -> d -> e) -> a -> b -> c -> d -> e Source #
Memoise a quaternary function, checking that the outermost table can be pruned.
uncheckedMemo2 :: (MemoArg a, MemoArg b) => (a -> b -> c) -> a -> b -> c Source #
Memoise a binary function, without checking that the outer table can be pruned.