Hey it works :D  <br>Here is a proof of concept:<br><a href="http://gist.github.com/189104">http://gist.github.com/189104</a><br><br>Maybe later today I&#39;ll try to make a version that can be safely used outside IO.<br><br>
- Job<br><br><br><div class="gmail_quote">On Fri, Sep 18, 2009 at 10:19 AM, Job Vranish <span dir="ltr">&lt;<a href="mailto:jvranish@gmail.com">jvranish@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Yeah it seems like the general solution to the problem would be some sort of map-like datastructure that you add items via a key/value pair, and if the key gets GC&#39;d, that entry gets removed from the structure.<br><br>

I&#39;ve been wanting something like this as well, but didn&#39;t know about weak references so I didn&#39;t know if it was possible, but I think I could make something like this now. I&#39;ll give it a shot and let you guys know how it goes.<br>

<br>Rodney could you post your memo code that uses the weak references?<br><font color="#888888"><br>- Job</font><div><div></div><div class="h5"><br><br><div class="gmail_quote">On Fri, Sep 18, 2009 at 7:56 AM, Peter Verswyvelen <span dir="ltr">&lt;<a href="mailto:bugfact@gmail.com" target="_blank">bugfact@gmail.com</a>&gt;</span> wrote:<br>

<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">I would also like to see a solution for problems like these.<br>
<br>
Haskell provides a lot of nice memoizing / caching data structures -<br>
like a trie - but the ones I know indeed keep growing, so no garbage<br>
collection takes place?<br>
<br>
It would be nice to have a data structure that performs caching but<br>
does not grow unlimited.<br>
<br>
I had a similar problem with stable names; it is not possible to check<br>
if a stable name is still &quot;alive&quot;.<br>
<div><div></div><div><br>
On Fri, Sep 18, 2009 at 1:39 AM, Rodney Price &lt;<a href="mailto:rodprice@raytheon.com" target="_blank">rodprice@raytheon.com</a>&gt; wrote:<br>
&gt; In my case, the results of each computation are used to generate a node<br>
&gt; in a graph structure (dag).  The key, oddly, is a hash of a two-tuple<br>
&gt; that gets stored in the data structure after the computation of the<br>
&gt; node finishes.  If I don&#39;t memoize the function to build a node, the<br>
&gt; cost of generating the tree is exponential; if I do, it&#39;s somewhere<br>
&gt; between linear and quadratic.<br>
&gt;<br>
&gt; Another process prunes parts of this graph structure as time goes on.<br>
&gt; The entire data structure is intended to be persistent, lasting for<br>
&gt; days at a time in a server-like application.  If the parts pruned<br>
&gt; aren&#39;t garbage collected, the space leak will eventually be<br>
&gt; catastrophic.  Either the memo table or the graph structure itself will<br>
&gt; outgrow available memory.<br>
&gt;<br>
&gt; -Rod<br>
&gt;<br>
&gt;<br>
&gt; On Thu, 17 Sep 2009 13:32:13 -0400<br>
&gt; Job Vranish &lt;<a href="mailto:jvranish@gmail.com" target="_blank">jvranish@gmail.com</a>&gt; wrote:<br>
&gt;<br>
&gt;&gt; What are you trying to use this for? It seems to me that for memo<br>
&gt;&gt; tables you almost never have references to they keys outside the<br>
&gt;&gt; lookup table since the keys are usually computed right at the last<br>
&gt;&gt; minute, and then discarded (otherwise it might be easier to just<br>
&gt;&gt; cache stuff outside the function).<br>
&gt;&gt;<br>
&gt;&gt; For example with a naive fibs, the values you are passing in are<br>
&gt;&gt; computed, and probably don&#39;t exist before you do the recursive call,<br>
&gt;&gt; and then are discarded shortly afterward.<br>
&gt;&gt;<br>
&gt;&gt; It seems like putting a cap on the cache size, and then just<br>
&gt;&gt; overwriting old entries would be better.<br>
&gt;&gt; Am I missing something?<br>
&gt;&gt;<br>
&gt;&gt; - Job<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; On Wed, Sep 16, 2009 at 4:48 PM, Rodney Price &lt;<a href="mailto:rodprice@raytheon.com" target="_blank">rodprice@raytheon.com</a>&gt;<br>
&gt;&gt; wrote:<br>
&gt;&gt;<br>
&gt;&gt; &gt; How does garbage collection work in an example like the one below?<br>
&gt;&gt; &gt; You memoize a function with some sort of lookup table, which stores<br>
&gt;&gt; &gt; function arguments as keys and function results as values.  As long<br>
&gt;&gt; &gt; as the function remains in scope, the keys in the lookup table<br>
&gt;&gt; &gt; remain in memory, which means that the keys themselves always<br>
&gt;&gt; &gt; remain reachable and they cannot be garbage collected.  Right?<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; So what do you do in the case where you know that, after some<br>
&gt;&gt; &gt; period of time, some entries in the lookup table will never be<br>
&gt;&gt; &gt; accessed?  That is, there are no references to the keys for some<br>
&gt;&gt; &gt; entries remaining, except for the references in the lookup table<br>
&gt;&gt; &gt; itself.  You&#39;d like to allow the memory occupied by the keys to be<br>
&gt;&gt; &gt; garbage collected.  Otherwise, if the function stays around for a<br>
&gt;&gt; &gt; long time, the size of the lookup table always grows.  How do you<br>
&gt;&gt; &gt; avoid the space leak?<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; I notice that there is a function in Data.IORef,<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; mkWeakIORef :: IORef a -&gt; IO () -&gt; IO (Weak (IORef a))<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; which looks promising.  In the code below, however, there&#39;s only one<br>
&gt;&gt; &gt; IORef, so either the entire table gets garbage collected or none of<br>
&gt;&gt; &gt; it does.<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; I&#39;ve been reading the paper &quot;Stretching the storage manager: weak<br>
&gt;&gt; &gt; pointers and stable names in Haskell,&quot; which seems to answer my<br>
&gt;&gt; &gt; question.  When I attempt to run the memoization code in the paper<br>
&gt;&gt; &gt; on the simple fib example, I find that -- apparently due to lazy<br>
&gt;&gt; &gt; evaluation -- no new entries are entered into the lookup table, and<br>
&gt;&gt; &gt; therefore no lookups are ever successful!<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; So apparently there is some interaction between lazy evaluation and<br>
&gt;&gt; &gt; garbage collection that I don&#39;t understand.  My head hurts.  Is it<br>
&gt;&gt; &gt; necessary to make the table lookup operation strict?  Or is it<br>
&gt;&gt; &gt; something entirely different that I am missing?<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; -Rod<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; On Thu, 10 Sep 2009 18:33:47 -0700<br>
&gt;&gt; &gt; Ryan Ingram &lt;<a href="mailto:ryani.spam@gmail.com" target="_blank">ryani.spam@gmail.com</a>&gt; wrote:<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; &gt;<br>
&gt;&gt; &gt; &gt; memoIO :: Ord a =&gt; (a -&gt; b) -&gt; IO (a -&gt; IO b)<br>
&gt;&gt; &gt; &gt; memoIO f = do<br>
&gt;&gt; &gt; &gt;    cache &lt;- newIORef M.empty<br>
&gt;&gt; &gt; &gt;    return $ \x -&gt; do<br>
&gt;&gt; &gt; &gt;        m &lt;- readIORef cache<br>
&gt;&gt; &gt; &gt;        case M.lookup x m of<br>
&gt;&gt; &gt; &gt;            Just y -&gt; return y<br>
&gt;&gt; &gt; &gt;            Nothing -&gt; do let res = f x<br>
&gt;&gt; &gt; &gt;                          writeIORef cache $ M.insert x res m<br>
&gt;&gt; &gt; &gt;                          return res<br>
&gt;&gt; &gt; &gt;<br>
&gt;&gt; &gt; &gt; memo :: Ord a =&gt; (a -&gt; b) -&gt; (a -&gt; b)<br>
&gt;&gt; &gt; &gt; memo f = unsafePerformIO $ do<br>
&gt;&gt; &gt; &gt;     fmemo &lt;- memoIO f<br>
&gt;&gt; &gt; &gt;     return (unsafePerformIO . fmemo)<br>
&gt;&gt; &gt; &gt;<br>
&gt;&gt; &gt; &gt; I don&#39;t think there is any valid transformation that breaks this,<br>
&gt;&gt; &gt; &gt; since the compiler can&#39;t lift anything through unsafePerformIO.<br>
&gt;&gt; &gt; &gt; Am I mistaken?<br>
&gt;&gt; &gt; &gt;<br>
&gt;&gt; &gt; &gt;   -- ryan<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; _______________________________________________<br>
&gt;&gt; &gt; Haskell-Cafe mailing list<br>
&gt;&gt; &gt; <a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
&gt;&gt; &gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
&gt;&gt; &gt;<br>
&gt;<br>
&gt; _______________________________________________<br>
&gt; Haskell-Cafe mailing list<br>
&gt; <a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
&gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
&gt;<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>
</div></div></blockquote></div><br>