On Thu, Mar 24, 2011 at 4:02 PM, Joshua Ball &lt;<a href="mailto:joshbball@gmail.com">joshbball@gmail.com</a>&gt; wrote:<br>&gt; Never mind. I figured it out on my own. Here&#39;s my solution for<br>&gt; posterity. There&#39;s probably a &quot;fix&quot; hiding in there somewhere - notice<br>

&gt; the new type of reduce.<br><br>Yep, there is:<br><br><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">&gt; force :: M.Map Key Chain -&gt; M.Map Key [Int]<br>&gt; force mp = ret where<br>&gt; ret = M.fromList (map (\k -&gt; (k, reduce mp (ret !) k)) (M.keys mp))<br>

  ^^^_________________________________________^^^</font><div><br></div><div><font class="Apple-style-span" face="arial, helvetica, sans-serif">There&#39;s your knot.  You could have written it like this:</font></div><div>

<font class="Apple-style-span" face="arial, helvetica, sans-serif"><br></font></div><div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">force mp = fix (\ret -&gt; M.fromList (map (\k -&gt; (k, reduce mp (ret !) k)) (M.keys mp))</font></div>

<div><br>&gt; reduce :: M.Map Key Chain -&gt; (Key -&gt; [Int]) -&gt; Key -&gt; [Int]<br>&gt; reduce mp lookup key = follow (mp ! key) where<br>&gt;  follow (Link i c) = i : follow c<br>&gt;  follow (Ref k) = lookup k<br>

&gt;  follow (Trace message c) = trace message (follow c)<br>&gt;<br>&gt; example = M.fromList [(Key &quot;ones&quot;, Link 1 . Trace &quot;expensive<br>&gt; computation here&quot; . Ref . Key $ &quot;ones&quot;)]<br>&gt;<br>

&gt; main = print $ take 10 $ (force example ! Key &quot;ones&quot;)<br>&gt;<br>&gt; On Thu, Mar 24, 2011 at 12:35 PM, Joshua Ball &lt;<a href="mailto:joshbball@gmail.com">joshbball@gmail.com</a>&gt; wrote:<br>&gt;&gt; {-<br>

&gt;&gt;  - Hi all,<br>&gt;&gt;  -<br>&gt;&gt;  - I&#39;m having trouble tying the recursive knot in one of my programs.<br>&gt;&gt;  -<br>&gt;&gt;  - Suppose I have the following data structures and functions:<br>&gt;&gt;  -}<br>

&gt;&gt; module Recursion where<br>&gt;&gt;<br>&gt;&gt; import Control.Monad.Fix<br>&gt;&gt; import Data.Map ((!))<br>&gt;&gt; import qualified Data.Map as M<br>&gt;&gt; import Debug.Trace<br>&gt;&gt;<br>&gt;&gt; newtype Key = Key { unKey :: String }<br>

&gt;&gt;  deriving (Eq, Ord, Show)<br>&gt;&gt;<br>&gt;&gt; data Chain = Link Int Chain | Trace String Chain | Ref Key<br>&gt;&gt;  deriving (Show)<br>&gt;&gt;<br>&gt;&gt; reduce :: M.Map Key Chain -&gt; Key -&gt; [Int]<br>

&gt;&gt; reduce env k = follow (env ! k) where<br>&gt;&gt;  follow (Link i c) = i : follow c<br>&gt;&gt;  follow (Ref k) = reduce env k<br>&gt;&gt;  follow (Trace message c) = trace message (follow c)<br>&gt;&gt;<br>&gt;&gt; -- Now I want a &quot;force&quot; function that expands all of the chains into<br>

&gt;&gt; int sequences.<br>&gt;&gt; force1, force2 :: M.Map Key Chain -&gt; M.Map Key [Int]<br>&gt;&gt;<br>&gt;&gt; -- This is pretty easy to do:<br>&gt;&gt; force1 mp = M.fromList (map (\k -&gt; (k, reduce mp k)) (M.keys mp))<br>

&gt;&gt;<br>&gt;&gt; -- But I want the int sequences to be lazy. The following example<br>&gt;&gt; illustrates that they are not:<br>&gt;&gt; example = M.fromList [(Key &quot;ones&quot;, Link 1 . Trace &quot;expensive<br>

&gt;&gt; computation here&quot; . Ref . Key $ &quot;ones&quot;)]<br>&gt;&gt; -- Run &quot;force1 example&quot; in ghci, and you will see the &quot;expensive<br>&gt;&gt; computation here&quot; messages interleaved with an infinite<br>

&gt;&gt; -- list of ones. I would prefer for the &quot;expensive computation&quot; to<br>&gt;&gt; happen only once.<br>&gt;&gt;<br>&gt;&gt; -- Here was my first attempt at regaining laziness:<br>&gt;&gt; fixpointee :: M.Map Key Chain -&gt; M.Map Key [Int] -&gt; M.Map Key [Int]<br>

&gt;&gt; fixpointee env mp = M.fromList (map (\k -&gt; (k, reduce env k)) (M.keys mp))<br>&gt;&gt;<br>&gt;&gt; force2 env = fix (fixpointee env)<br>&gt;&gt;<br>&gt;&gt; main = print $ force2 example<br>&gt;&gt;<br>&gt;&gt; {-<br>

&gt;&gt;  - However, this gets stuck in an infinite loop and doesn&#39;t make it<br>&gt;&gt; past printing &quot;fromList &quot;.<br>&gt;&gt;  - (It was not difficult for me to see why, once I thought about it.)<br>&gt;&gt;  -<br>

&gt;&gt;  - How do I recover laziness? A pure solution would be nice, but in<br>&gt;&gt; the actual program<br>&gt;&gt;  - I am working on, I am in the IO monad, so I am ok with an impure solution.<br>&gt;&gt;  - It&#39;s also perfectly ok for me to modify the reduce function.<br>

&gt;&gt;  -<br>&gt;&gt;  - Thanks in advance for you help,<br>&gt;&gt;  - Josh &quot;Ua&quot; Ball<br>&gt;&gt;  -}<br>&gt;&gt;<br>&gt;<br>&gt; _______________________________________________<br>&gt; Haskell-Cafe mailing list<br>

&gt; <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>&gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>&gt;<br><br></div>