Hi,
I have tried to implement a memo function using stable names and weak
pointers like it is presented in the paper "stretching the storage
manager". There is an abstract datatype SNMap a b which implements a
map that maps values of type StableName a to values of type b. The map
is located in an IORef.
{-# NOINLINE memo #-}
memo :: (a -> b) -> a -> b
memo f =
unsafePerformIO (do
tref <- newSNMap
return (applyWeak f tref))
{-# NOINLINE applyWeak #-}
applyWeak :: (a -> b) -> SNMap a (Weak b) -> a -> b
applyWeak f tbl arg =
unsafePerformIO (do
sn <- makeStableName arg
lkp <- lookupSNMap tbl sn
case lkp of
Nothing -> not_found sn
Just weak -> do
val <- deRefWeak weak
case val of
Just result -> return result
Nothing -> not_found sn)
where
not_found sn = do
let res = f arg
weak <- mkWeak arg res Nothing
insertSNMap tbl sn weak
return res
Using this memo function I have implemented a fibonacci function like
it is defined in the paper.
fib :: Int -> Int
fib = memo ufib
ufib :: Int -> Int
ufib 0 = 1
ufib 1 = 1
ufib n = fib (n-1) + fib (n-2)
When I compile this program with 6.10.3 fib yields the correct results
up to 18 but for 19 it detects a loop.
Can anybody give me a hint how I can avoid this behaviour (and still
use unsafePerformIO ; ) )?
Cheers, Jan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
