-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hello everyone, I am trying to write a generalisation of memoisation for a couple of backtracking algorithms that I wrote (which don't specify a memoisation technique), by keeping a local destructive update using unsafePerformIO and IORef - neither of which I have used before and I am struggling to figure out. I am going from the document: http://haskell.org/hawiki/GlobalMutableState I am not sure if: a) this is even possible b) if a) holds, if this is a good thing Here is some code to help demonstrate what I intend: {-# OPTIONS_GHC -fglasgow-exts #-} import Data.Ix - -- implementations must guarantee that - -- memo f k is equivalent to f k - -- but may otherwise use local destructive updates class Memo k v where memo :: (k -> v) -> k -> v instance (Ix k) => Memo k v where memo f k = error("todo: array") instance (Ord k) => Memo k v where memo f k = error("todo: binary tree") - -- Tony Morris http://tmorris.net/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGkZlFmnpgrYe6r60RArT8AJ4iFVyzmUN1pdxpMBokZpj48CiqRgCfReIe 2yZ55LMcFs24TJOVeCV4tbo= =IR5s -----END PGP SIGNATURE-----
You might look at this paper: http://research.microsoft.com/Users/simonpj/Papers/weak.htm "Stretching the storage manager: weak pointers and stable names in Haskell" - Simon Peyton Jones, Simon Marlow, and Conal Elliott, IFL'99. It describes a solution to exactly the problem you're trying to solve, that's implemented in GHC. It may not be the right thing for you, but you may be interested to see previous approaches to the problem in any case. Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "Poor man wanna be rich, rich man wanna be king, the king ain't satisfied until he rules everything" -- Bruce Springsteen
Funny that you mention using unsafePerformIO to do memoizing; I just implemented it a couple of days ago to familiarize myself with techniques that use global state. Here's my implementation which uses trees (Data.Map). module Memoize (memoize, memoizefix) where import System.IO.Unsafe import qualified Data.Map as Map import Data.IORef memoized :: Ord a => IORef (Map.Map a b) -> (a -> b) -> a -> b memoized memTbl f a = unsafePerformIO $ do memo <- readIORef memTbl catch (Map.lookup a memo) $ \_ -> do let ans = f a let memo' = Map.insert a ans memo writeIORef memTbl memo' return ans memoize :: Ord a => (a -> b) -> (a -> b) memoize f = unsafePerformIO $ do memTbl <- newIORef Map.empty return $ memoized memTbl f memFix :: Ord a => IORef (Map.Map a b) -> ((a -> b) -> (a -> b)) -> (a -> b) memFix memTbl f = let x = f (memoized memTbl x) in x memoizefix :: Ord a => ((a -> b) -> (a -> b)) -> (a -> b) memoizefix f = unsafePerformIO $ do memTbl <- newIORef Map.empty return $ memFix memTbl f A test case: module Main where import Memoize fix f = let x = f x in x nfibr f x = if x <= 1 then (1::Integer) else f (x-1) + f (x-2) nfib = fix nfibr mfib = memoizefix nfibr main = sequence_ $ map (print . mfib) [1..] (compare replacing mfib with nfib in main). I think you'll have problems with overlapping instances with your Ix/Ord instance declarations; better to not use typeclasses there and just have memoIx and memoTree, I think. I am a bit nervous about what happens if you turn optimizations on; you might need to sprinkle a few {-# NOINLINE function_name #-} pragmas into Memoize.hs to make sure it works properly in a real codebase, but it's a good start. -- ryan
participants (3)
-
Ryan Ingram -
Tim Chevalier -
Tony Morris