stable-memo (empty) → 0.1.1

raw patch · 6 files changed

+225/−0 lines, 6 filesdep +basedep +hashtablesdep +taggedsetup-changed

Dependencies added: base, hashtables, tagged

Files

• Data/StableMemo.hs +31/−0
• Data/StableMemo/Internal.hs +61/−0
• Data/StableMemo/Weak.hs +32/−0
• LICENSE +20/−0
• Setup.hs +2/−0
• stable-memo.cabal +79/−0

@@ -0,0 +1,31 @@+{-# LANGUAGE BangPatterns #-}+module Data.StableMemo (memo, memo2, memo3) where++import Data.Proxy++import System.Mem.Weak (Weak)++import qualified Data.StableMemo.Internal as Internal+import qualified System.Mem.Weak as Weak++data Strong a = Strong a !(Weak a)++instance Internal.Ref Strong where+  mkRef _ y final = do+    weak <- Weak.mkWeakPtr y $ Just final+    return $ Strong y weak+  deRef (Strong x _) = return $ Just x+  finalize (Strong _ weak) = Weak.finalize weak++-- | Memoize a unary function.+memo :: (a -> b) -> (a -> b)+{-# NOINLINE memo #-}+memo = Internal.memo (Proxy :: Proxy Strong)++-- | Curried memoization to share partial evaluation+memo2 :: (a -> b -> c) -> (a -> b -> c)+memo2 f = memo . memo f++-- | Curried memoization to share partial evaluation+memo3 :: (a -> b -> c -> d) -> (a -> b -> c -> d)+memo3 f = memo . memo2 f

@@ -0,0 +1,61 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE KindSignatures #-}+module Data.StableMemo.Internal (Ref (..), memo) where++import Data.Proxy+import System.Mem.StableName++import Data.HashTable.IO (BasicHashTable)+import System.IO.Unsafe (unsafePerformIO)+import System.Mem.Weak (Weak)++import qualified Data.HashTable.IO as HashTable+import qualified System.Mem.Weak as Weak++type SNMap a b = BasicHashTable (StableName a) b+type MemoTable ref a b = SNMap a (ref b)++class Ref ref where+  mkRef    :: a -> b -> IO () -> IO (ref b)+  deRef    :: ref a -> IO (Maybe a)+  finalize :: ref a -> IO ()++instance Ref Weak where+  mkRef x y = Weak.mkWeak x y . Just+  deRef = Weak.deRefWeak+  finalize = Weak.finalize++finalizer :: StableName a -> Weak (MemoTable ref a b) -> IO ()+finalizer sn weakTbl = do+  r <- Weak.deRefWeak weakTbl+  case r of+    Nothing -> return ()+    Just tbl -> HashTable.delete tbl sn++memo' :: Ref ref => Proxy ref -> (a -> b) -> MemoTable ref a b -> Weak (MemoTable ref a b) -> (a -> b)+memo' _ f tbl weakTbl !x = unsafePerformIO $ do+  sn <- makeStableName x+  lkp <- HashTable.lookup tbl sn+  case lkp of+    Nothing -> notFound sn+    Just w -> do+      maybeVal <- deRef w+      case maybeVal of+        Nothing -> notFound sn+        Just val -> return val+  where notFound sn = do+          let y = f x+          weak <- mkRef x y $ finalizer sn weakTbl+          HashTable.insert tbl sn weak+          return y++tableFinalizer :: Ref ref => MemoTable ref a b -> IO ()+tableFinalizer = HashTable.mapM_ $ finalize . snd++memo :: Ref ref => Proxy (ref :: * -> *) -> (a -> b) -> (a -> b)+memo p f =+  let (tbl, weak) = unsafePerformIO $ do+        tbl' <- HashTable.new+        weak' <- Weak.mkWeakPtr tbl . Just $ tableFinalizer tbl+        return (tbl', weak')+  in memo' p f tbl weak

@@ -0,0 +1,32 @@+{-|+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.+-}++{-# LANGUAGE BangPatterns #-}+module Data.StableMemo.Weak (memo, memo2, memo3) where++import Data.Proxy++import System.Mem.Weak (Weak)++import qualified Data.StableMemo.Internal as Internal++-- | Memoize a unary function.+memo :: (a -> b) -> (a -> b)+{-# NOINLINE memo #-}+memo = Internal.memo (Proxy :: Proxy Weak)++-- | Curried memoization to share partial evaluation+memo2 :: (a -> b -> c) -> (a -> b -> c)+memo2 f = memo . memo f++-- | Curried memoization to share partial evaluation+memo3 :: (a -> b -> c -> d) -> (a -> b -> c -> d)+memo3 f = memo . memo2 f

@@ -0,0 +1,20 @@+Copyright (C) 2012 Jake McArthur++Permission is hereby granted, free of charge, to any person obtaining+a copy of this software and associated documentation files (the+"Software"), to deal in the Software without restriction, including+without limitation the rights to use, copy, modify, merge, publish,+distribute, sublicense, and/or sell copies of the Software, and to+permit persons to whom the Software is furnished to do so, subject to+the following conditions:++The above copyright notice and this permission notice shall be+included in all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE+LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION+OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION+WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,79 @@+name:                stable-memo+version:             0.1.1+synopsis:            Memoization based on argument identity+license:             MIT+license-file:        LICENSE+author:              Jake McArthur <Jake.McArthur@gmail.com>+maintainer:          Jake McArthur <Jake.McArthur@gmail.com>+category:            Data+build-type:          Simple+cabal-version:       >=1.10+description:++  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).++  .++  * 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.++  .++  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 strict 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++  .++  This implementation is largely based on the one 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>).++library+  build-depends:       base >=4.6 && <5, hashtables ==1.0.*, tagged ==0.4.*+  default-language:    Haskell2010+  exposed-modules:     Data.StableMemo, Data.StableMemo.Weak+  other-extensions:    BangPatterns+  other-modules:       Data.StableMemo.Internal++source-repository head+  type:     darcs+  location: http://patch-tag.com/r/jmcarthur/stable-memo++source-repository this+  type:     darcs+  location: http://patch-tag.com/r/jmcarthur/stable-memo+  tag:      v0.1.1