stable-memo: Memoization based on argument identity
Whereas most memo combinators memoize based on equality, stable-memo does it based on whether the exact same argument has been passed to the function before (that is, is the same argument in memory).
stable-memo only evaluates keys to WHNF.
This can be more suitable for recursive functions over graphs with cycles.
stable-memo doesn't retain the keys it has seen so far, which allows them to be garbage collected if they will no longer be used. Finalizers are put in place to remove the corresponding entries from the memo table if this happens.
Data.StableMemo.Weak provides an alternative set of combinators that also avoid retaining the results of the function, only reusing results if they have not yet been garbage collected.
There is no type class constraint on the function's argument.
For motivation, here is an implementation of map that preserves sharing of the spine for cyclic lists. It should even be safe to use this on arbitrarily long, acyclic lists since as long as the garbage collector is chasing you, the size of the memo table should stay under control, too.
map :: (a -> b) -> [a] -> [b] map f = go where go = memo map' map' [] = [] map' (x:xs) = f x : go xs
This library is largely based on the implementation of memo found in "Stretching the storage manager: weak pointers and stable names in Haskell", from Simon Peyton Jones, Simon Marlow, and Conal Elliott (http://community.haskell.org/~simonmar/papers/weak.pdf).
Downloads
- stable-memo-0.4.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
Versions [RSS] | 0.1.1, 0.1.2, 0.1.3, 0.2.0, 0.2.1, 0.2.2, 0.2.3, 0.2.4, 0.3.0, 0.3.1, 0.4.0 |
---|---|
Dependencies | base (>=4.6 && <4.19), ghc-prim (>=0.3 && <0.11), hashtables (>=1.0 && <1.4), tagged (>=0.7 && <0.8) [details] |
Tested with | ghc ==7.6.3, ghc ==7.8.4, ghc ==7.10.3, ghc ==8.0.2, ghc ==8.2.2, ghc ==8.4.4, ghc ==8.6.5, ghc ==8.8.4, ghc ==8.10.7, ghc ==9.0.2, ghc ==9.2.7, ghc ==9.4.4, ghc ==9.6.1 |
License | MIT |
Author | Jake McArthur <Jake.McArthur@gmail.com> |
Maintainer | Jake McArthur <Jake.McArthur@gmail.com> |
Category | Data |
Home page | https://github.com/jmcarthur/stable-memo |
Bug tracker | https://github.com/jmcarthur/stable-memo/issues |
Source repo | head: git clone https://github.com/jmcarthur/stable-memo.git this: git clone https://github.com/jmcarthur/stable-memo.git(tag v0.4.0) |
Uploaded | by JakeMcArthur at 2023-08-14T00:03:12Z |
Distributions | NixOS:0.4.0 |
Reverse Dependencies | 1 direct, 0 indirect [details] |
Downloads | 7841 total (3 in the last 30 days) |
Rating | (no votes yet) [estimated by Bayesian average] |
Your Rating | |
Status | Docs available [build log] Last success reported on 2023-08-14 [all 1 reports] |