4 ms·

Check out the source for, e.g. http://hackage.haskell.org/package/stringtable-atom http://hackage.haskell.org/package/stringtable-atom There are a number of g

Check out the source for, e.g. http://hackage.haskell.org/package/stringtable-atom http://hackage.haskell.org/package/stringtable-atom There are a number of generalized memoization libraries. This one http://hackage.haskell.org/package/data-memocombinators http://hackage.haskell.org/package/data-memocombinators doesn't use `unsafePeformIO`, but instead imports the Array package. If you check out http://hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/src/Data-Array-Base.html http://hackage.haskell.org/packages/archive/array/0.2.0.0/do... you will find 696 uses of "unsafe" in one module... http://hackage.haskell.org/package/MemoTrie http://hackage.haskell.org/package/MemoTrie by contrast takes a different approach.

joeyh 16y ago
AFAICS, there is no unsafePerformIO in any of the above except for stringtable-atom. AIUI, it's possible to implement generalized memoization in haskell w/o unsafePerformIO, and both memocombinators and MemTrie do so. I take your point that if necessary, they could have been written to use unsafePerformIO, and as long as the library authors know what they're doing, and are careful, that would be OK. So, you don't actually need to read CS papers to do memoization in haskell. You just need to know that the libraries that do it have "memo", not "memoize" in their names. This stuff, could, perhaps be easier to find.
- applicative 16y ago
  You are repeating what I said. I was defending the use of `unsafePerformIO` as a non-'hack', and perhaps I misunderstood you to be thinking otherwise. The memocombinators library uses Array, which uses `unsafePerformIO` and friends almost 700 times in one module. MemTrie takes a different approach, one not using unsafePerformIO; maybe I wasn't clear that was my meaning. In any case, there is little need for a library, at least for the simplest idea of memoization (the ugly Reddit discussion suggests there are many things to be meant.) It is just a case of writing down what is meant, as happens a few times in slightly different ways on the reddit page, off the top of peoples' heads. So for example this one: memo :: Eq k => (k -> v) -> k -> v memo f = unsafePerformIO $ do ref <- newIORef [] :: IO (IORef [(k,v)]) -- make a page for a table return $ \k -> unsafePerformIO $ do -- when f is applied to k memotable <- readIORef ref -- get out the table case lookup k memotable of -- see if k has been done Just x -> return x -- if it has, we're done! Nothing -> do -- if it hasn't let a = f k -- calculate f k atomicModifyIORef ref $ \t -> ((k,a):t,()) -- add it to the table before return a -- returning f k This is someone's brief treatment, which meets most of the definitions people were using. The clojure procedure is more powerful; as far as I can see, getting something similar in Haskell requires a bit more subtlety.

joeyh 16y ago

AFAICS, there is no unsafePerformIO in any of the above except for stringtable-atom. AIUI, it's possible to implement generalized memoization in haskell w/o unsafePerformIO, and both memocombinators and MemTrie do so. I take your point that if necessary, they could have been written to use unsafePerformIO, and as long as the library authors know what they're doing, and are careful, that would be OK. So, you don't actually need to read CS papers to do memoization in haskell. You just need to know that the libraries that do it have "memo", not "memoize" in their names. This stuff, could, perhaps be easier to find.

applicative 16y ago
You are repeating what I said. I was defending the use of `unsafePerformIO` as a non-'hack', and perhaps I misunderstood you to be thinking otherwise. The memocombinators library uses Array, which uses `unsafePerformIO` and friends almost 700 times in one module. MemTrie takes a different approach, one not using unsafePerformIO; maybe I wasn't clear that was my meaning. In any case, there is little need for a library, at least for the simplest idea of memoization (the ugly Reddit discussion suggests there are many things to be meant.) It is just a case of writing down what is meant, as happens a few times in slightly different ways on the reddit page, off the top of peoples' heads. So for example this one: memo :: Eq k => (k -> v) -> k -> v memo f = unsafePerformIO $ do ref <- newIORef [] :: IO (IORef [(k,v)]) -- make a page for a table return $ \k -> unsafePerformIO $ do -- when f is applied to k memotable <- readIORef ref -- get out the table case lookup k memotable of -- see if k has been done Just x -> return x -- if it has, we're done! Nothing -> do -- if it hasn't let a = f k -- calculate f k atomicModifyIORef ref $ \t -> ((k,a):t,()) -- add it to the table before return a -- returning f k This is someone's brief treatment, which meets most of the definitions people were using. The clojure procedure is more powerful; as far as I can see, getting something similar in Haskell requires a bit more subtlety.