<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
</head>
<body bgcolor="#ffffff" text="#000000">
<font face="Helvetica, Arial, sans-serif">Hi,<br>
<br>
in SOE, the following memoization function is implemented:<br>
</font>
<link type="text/css" rel="stylesheet" href="hscolour.css">
<pre><span class="varid">memo1</span> <span class="keyglyph">::</span> <span
 class="layout">(</span><span class="varid">a</span><span
 class="keyglyph">-&gt;</span><span class="varid">b</span><span
 class="layout">)</span> <span class="keyglyph">-&gt;</span> <span
 class="layout">(</span><span class="varid">a</span><span
 class="keyglyph">-&gt;</span><span class="varid">b</span><span
 class="layout">)</span>
<span class="varid">memo1</span> <span class="varid">f</span> <span
 class="keyglyph">=</span> <span class="varid">unsafePerformIO</span> <span
 class="varop">$</span> <span class="keyword">do</span>
  <span class="varid">cache</span> <span class="keyglyph">&lt;-</span> <span
 class="varid">newIORef</span> <span class="keyglyph">[</span><span
 class="keyglyph">]</span>
  <span class="varid">return</span> <span class="varop">$</span> <span
 class="keyglyph">\</span><span class="varid">x</span> <span
 class="keyglyph">-&gt;</span> <span class="varid">unsafePerformIO</span> <span
 class="varop">$</span> <span class="keyword">do</span>
              <span class="varid">vals</span> <span class="keyglyph">&lt;-</span> <span
 class="varid">readIORef</span> <span class="varid">cache</span>
              <span class="keyword">case</span> <span class="varid">x</span> <span
 class="varop">`inCache`</span> <span class="varid">vals</span> <span
 class="keyword">of</span>
                <span class="conid">Nothing</span> <span
 class="keyglyph">-&gt;</span> <span class="keyword">do</span> <span
 class="keyword">let</span> <span class="varid">y</span> <span
 class="keyglyph">=</span> <span class="varid">f</span> <span
 class="varid">x</span>
                              <span class="varid">writeIORef</span> <span
 class="varid">cache</span> <span class="keyglyph">[</span><span
 class="layout">(</span><span class="varid">x</span><span class="layout">,</span><span
 class="varid">y</span><span class="layout">)</span><span
 class="keyglyph">]</span> <span class="comment">-- ((x,y) : </span>
<span class="comment">--                                if null vals then [] else [head vals])</span>
                              <span class="varid">return</span> <span
 class="varid">y</span>
                <span class="conid">Just</span> <span class="varid">y</span>  <span
 class="keyglyph">-&gt;</span> <span class="keyword">do</span> <span
 class="varid">return</span> <span class="varid">y</span>

<span class="varid">inCache</span> <span class="keyglyph">::</span> <span
 class="varid">a</span> <span class="keyglyph">-&gt;</span> <span
 class="keyglyph">[</span><span class="layout">(</span><span
 class="varid">a</span><span class="layout">,</span><span class="varid">b</span><span
 class="layout">)</span><span class="keyglyph">]</span> <span
 class="keyglyph">-&gt;</span> <span class="conid">Maybe</span> <span
 class="varid">b</span>
<span class="varid">x</span> <span class="varop">`inCache`</span> <span
 class="keyglyph">[</span><span class="keyglyph">]</span> <span
 class="keyglyph">=</span> <span class="conid">Nothing</span>
<span class="varid">x</span> <span class="varop">`inCache`</span> <span
 class="layout">(</span><span class="layout">(</span><span class="varid">x'</span><span
 class="layout">,</span><span class="varid">y'</span><span
 class="layout">)</span><span class="conop">:</span><span class="varid">xys</span><span
 class="layout">)</span> <span class="keyglyph">=</span>
   <span class="keyword">if</span> <span class="varid">unsafePtrEq</span> <span
 class="varid">x</span> <span class="varid">x'</span> <span
 class="keyword">then</span> <span class="conid">Just</span> <span
 class="varid">y'</span> <span class="keyword">else</span> <span
 class="varid">x</span> <span class="varop">`inCache`</span> <span
 class="varid">xys

</span></pre>
<font face="Helvetica, Arial, sans-serif">This is then used in<br>
<br>
</font><tt>type Time = Float<br>
</tt><tt>type UserAction = G.Event<br>
<br>
data G.Event <br>
&nbsp; = Key Char Bool<br>
&nbsp; | Button Point Bool Bool<br>
&nbsp; | MouseMove Point<br>
&nbsp; | Resize<br>
&nbsp; | Closed<br>
&nbsp; deriving Show <br>
<br>
</tt><tt>newtype Behavior a&nbsp; = Behavior (([Maybe UserAction],[Time])
-&gt; [a])<br>
newtype Event a&nbsp; = Event (([Maybe UserAction],[Time]) -&gt; [Maybe a])<br>
</tt><font face="Helvetica, Arial, sans-serif"><br>
</font><tt>Behavior fb `untilB` Event fe =<br>
&nbsp; memoB $ Behavior (\uts@(us,ts) -&gt; loop us ts (fe uts) (fb uts))<br>
&nbsp;&nbsp;&nbsp; where loop (_:us) (_:ts) ~(e:es) (b:bs) =<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b : case e of <br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Nothing&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; -&gt; loop us ts es bs<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Just (Behavior fb') -&gt; fb' (us,ts)<br>
<br>
memoB :: Behavior a -&gt; Behavior a<br>
memoB (Behavior fb) = Behavior (memo1 fb)<br>
</tt><font face="Helvetica, Arial, sans-serif"><br>
</font><big><tt></tt><tt><br>
</tt></big><font face="Helvetica, Arial, sans-serif">If I understand it
correctly, the memoization is required because otherwise recursive
"streams" wouldn't work. For example, in the Pong game example, a
ballPositionX stream is generated by integrating a ballVelocityX
stream, but the ballVelocityX stream changes sign when the ball hits
the left or right walls, and to determine that event, the ballPositionX
stream is required. So both streams are mutually recursive, and without
memoization, the program would be stuck (at least my own FRP
experiments, which don't use memoization yet, gets stuck :-)). Another
trick to prevent this, is the "</font><tt>b : case e of" </tt><font
 face="Helvetica, Arial, sans-serif">code in untilB, which causes the
event to be handled a bit too late, to avoid cyclic interdependencies.<br>
</font><font face="Helvetica, Arial, sans-serif"><br>
I hope I got that right. Now my questions.<br>
<br>
So, </font><font face="Helvetica, Arial, sans-serif">the keys (x) and
values (y) in (memo1 fb)&nbsp; are streams (aka infinite lists)? More
correctly, memo1 uses a pointer to the head of the list as a key, for
fast comparing (as you can't compare infinite lists)? But since both
key and value are infinite
streams, won't this approach cause a serious space leak because the
whole list cannot be reclaimed by the garbage collector? So the full
ballPositionX and ballVelocityX streams would remain in memory, until
the program exits?<br>
<br>
Since this
doesn't happen when I run the SOE examples (I guess!), I clearly
misunderstand this whole thing. I could explain it when the pointer to
the list is actually a pointer to the delayed computation (a "thunk"?)
of the tail, but the code doesn't seem to do that.<br>
<br>
</font><font face="Helvetica, Arial, sans-serif">Thanks for any help, I
hope I explained the problem well enough.<br>
<br>
Peter Verswyvelen<br>
<br>
<br>
<br>
<br>
<br>
<br>
</font><br>
</body>
</html>