stable-memo 0.2.2 → 0.2.3
raw patch · 5 files changed
+93/−42 lines, 5 files
Files
- Data/StableMemo.hs +61/−2
- Data/StableMemo/Internal.hs +3/−2
- Data/StableMemo/Weak.hs +20/−12
- LICENSE +1/−1
- stable-memo.cabal +8/−25
Data/StableMemo.hs view
@@ -1,6 +1,65 @@-{-# LANGUAGE BangPatterns #-}-{-# LANGUAGE Rank2Types #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE Safe #-} {-# LANGUAGE TypeOperators #-}++{-|+Module : Data.StableMemo+Copyright : (c) 2012, 2014 Jake McArthur+License : MIT+Maintainer : Jake McArthur <Jake.McArthur@gmail.com>+Stability : provisional+Portability : GHC++This module provides a small set of functions for memoization.+Whereas most memo combinators memoize based on equality, these do+it based on whether the exact same argument has been passed to+the function before (that is, is the same argument in memory).++* They only evaluate keys to WHNF.++* Relative to value-base memoization, this can be more suitable+ for recursive functions over graphs with cycles.++* These don't retain the keys they have seen so far, which allows+ mappings 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.++These will not work for arguments which happen to have the same+value but are not the same heap object. This rules out many+candidates for memoization, such as the most common example, the+naive Fibonacci implementation whose domain is machine Ints; it+can still be made to work for some domains, though, such as the+lazy naturals.++> data Nat = Succ Nat | Zero+>+> fib :: Nat -> Integer+> fib = memo fib'+> where fib' Zero = 0+> fib' (Succ Zero) = 1+> fib' (Succ n1@(Succ n2)) = fib n1 + fib n2++ Below 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+-}+ module Data.StableMemo (memo, memo2, memo3, (-->) (), memoPoly) where import Control.Applicative
Data/StableMemo/Internal.hs view
@@ -1,6 +1,7 @@ {-# LANGUAGE BangPatterns #-}-{-# LANGUAGE KindSignatures #-}-{-# LANGUAGE Rank2Types #-}+{-# LANGUAGE PolyKinds #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE Trustworthy #-} {-# LANGUAGE TypeOperators #-} module Data.StableMemo.Internal (Ref (..), Strong (..), (-->) (), memo) where
Data/StableMemo/Weak.hs view
@@ -1,17 +1,25 @@+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE Safe #-}+{-# LANGUAGE TypeOperators #-}+ {-|-This module provides memo combinators with slightly different behavior-from those in "Data.StableMemo". The memo tables generated by these-combinators use weak pointers to store the values, so they not only do-not unnecessarily retain the arguments, but they also do not retain-the function outputs. This can be useful for memoized functions that-are expected to be around for a long time. If the result for an input-has already been computed and happens to still be in the heap, it will-be reused, otherwise it will be recomputed.--}+Module : Data.StableMemo.Weak+Copyright : (c) 2012, 2014 Jake McArthur+License : MIT+Maintainer : Jake McArthur <Jake.McArthur@gmail.com>+Stability : provisional+Portability : GHC -{-# LANGUAGE BangPatterns #-}-{-# LANGUAGE Rank2Types #-}-{-# LANGUAGE TypeOperators #-}+This module provides memo combinators with slightly different+behavior from those in "Data.StableMemo". The memo tables+generated by these combinators use weak pointers to store the+values, so they not only do not unnecessarily retain the+arguments, but they also do not retain the function outputs. This+can be useful for memoized functions that are expected to be+around for a long time. If the result for an input has already+been computed and happens to still be in the heap, it will be+reused, otherwise it will be recomputed.+-} module Data.StableMemo.Weak (memo, memo2, memo3, (-->) (), memoPoly) where import Control.Applicative
LICENSE view
@@ -1,4 +1,4 @@-Copyright (C) 2012 Jake McArthur+Copyright (c) 2012, 2014 Jake McArthur Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the
stable-memo.cabal view
@@ -1,5 +1,5 @@ name: stable-memo-version: 0.2.2+version: 0.2.3 synopsis: Memoization based on argument identity license: MIT license-file: LICENSE@@ -42,28 +42,9 @@ . - stable-memo will not work for arguments which happen to have the- same value but are not the same heap object. This rules out many- candidates for memoization, such as the most common example, the- naive Fibonacci implementation whose domain is machine Ints; it can- still be made to work for some domains, though, such as the lazy- naturals.-- .-- > data Nat = Succ Nat | Zero- >- > fib :: Nat -> Integer- > fib = memo fib'- > where fib' Zero = 0- > fib' (Succ Zero) = 1- > fib' (Succ n1@(Succ n2)) = fib n1 + fib n2-- .-- Below 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+ 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. @@ -90,8 +71,10 @@ default-language: Haskell2010 exposed-modules: Data.StableMemo, Data.StableMemo.Weak other-extensions: BangPatterns,- KindSignatures,- Rank2Types,+ RankNTypes,+ PolyKinds,+ Safe,+ Trustworthy, TypeOperators other-modules: Data.StableMemo.Internal