On Thu, Mar 24, 2011 at 4:02 PM, Joshua Ball <<a href="mailto:joshbball@gmail.com">joshbball@gmail.com</a>> wrote:<br>> Never mind. I figured it out on my own. Here's my solution for<br>> posterity. There's probably a "fix" hiding in there somewhere - notice<br>
> the new type of reduce.<br><br>Yep, there is:<br><br><font class="Apple-style-span" face="'courier new', monospace">> force :: M.Map Key Chain -> M.Map Key [Int]<br>> force mp = ret where<br>> ret = M.fromList (map (\k -> (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'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="'courier new', monospace">force mp = fix (\ret -> M.fromList (map (\k -> (k, reduce mp (ret !) k)) (M.keys mp))</font></div>
<div><br>> reduce :: M.Map Key Chain -> (Key -> [Int]) -> Key -> [Int]<br>> reduce mp lookup key = follow (mp ! key) where<br>> follow (Link i c) = i : follow c<br>> follow (Ref k) = lookup k<br>
> follow (Trace message c) = trace message (follow c)<br>><br>> example = M.fromList [(Key "ones", Link 1 . Trace "expensive<br>> computation here" . Ref . Key $ "ones")]<br>><br>
> main = print $ take 10 $ (force example ! Key "ones")<br>><br>> On Thu, Mar 24, 2011 at 12:35 PM, Joshua Ball <<a href="mailto:joshbball@gmail.com">joshbball@gmail.com</a>> wrote:<br>>> {-<br>
>> - Hi all,<br>>> -<br>>> - I'm having trouble tying the recursive knot in one of my programs.<br>>> -<br>>> - Suppose I have the following data structures and functions:<br>>> -}<br>
>> module Recursion where<br>>><br>>> import Control.Monad.Fix<br>>> import Data.Map ((!))<br>>> import qualified Data.Map as M<br>>> import Debug.Trace<br>>><br>>> newtype Key = Key { unKey :: String }<br>
>> deriving (Eq, Ord, Show)<br>>><br>>> data Chain = Link Int Chain | Trace String Chain | Ref Key<br>>> deriving (Show)<br>>><br>>> reduce :: M.Map Key Chain -> Key -> [Int]<br>
>> reduce env k = follow (env ! k) where<br>>> follow (Link i c) = i : follow c<br>>> follow (Ref k) = reduce env k<br>>> follow (Trace message c) = trace message (follow c)<br>>><br>>> -- Now I want a "force" function that expands all of the chains into<br>
>> int sequences.<br>>> force1, force2 :: M.Map Key Chain -> M.Map Key [Int]<br>>><br>>> -- This is pretty easy to do:<br>>> force1 mp = M.fromList (map (\k -> (k, reduce mp k)) (M.keys mp))<br>
>><br>>> -- But I want the int sequences to be lazy. The following example<br>>> illustrates that they are not:<br>>> example = M.fromList [(Key "ones", Link 1 . Trace "expensive<br>
>> computation here" . Ref . Key $ "ones")]<br>>> -- Run "force1 example" in ghci, and you will see the "expensive<br>>> computation here" messages interleaved with an infinite<br>
>> -- list of ones. I would prefer for the "expensive computation" to<br>>> happen only once.<br>>><br>>> -- Here was my first attempt at regaining laziness:<br>>> fixpointee :: M.Map Key Chain -> M.Map Key [Int] -> M.Map Key [Int]<br>
>> fixpointee env mp = M.fromList (map (\k -> (k, reduce env k)) (M.keys mp))<br>>><br>>> force2 env = fix (fixpointee env)<br>>><br>>> main = print $ force2 example<br>>><br>>> {-<br>
>> - However, this gets stuck in an infinite loop and doesn't make it<br>>> past printing "fromList ".<br>>> - (It was not difficult for me to see why, once I thought about it.)<br>>> -<br>
>> - How do I recover laziness? A pure solution would be nice, but in<br>>> the actual program<br>>> - I am working on, I am in the IO monad, so I am ok with an impure solution.<br>>> - It's also perfectly ok for me to modify the reduce function.<br>
>> -<br>>> - Thanks in advance for you help,<br>>> - Josh "Ua" Ball<br>>> -}<br>>><br>><br>> _______________________________________________<br>> Haskell-Cafe mailing list<br>
> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>><br><br></div>