<div dir="ltr"><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div><font face="courier new,monospace">I wrote some code as part of my effort to do backtracking search of musical structures. Most recently I wrote a function that "pruned" the search tree by looking for illegal combinations of notes. In the interest of efficiency I wanted this algorithm to terminate as soon as it encountered an illegal combination rather than hunt the entire structure for every illegality. This made me think of the laziness of "or": a function like<br>
<br></font></div><font face="courier new,monospace">g = x || y || z<br><br></font></div><font face="courier new,monospace">will not evaluate y and z if x turns out to be true. <br><br></font></div><font face="courier new,monospace">I was also writing this code within a stack of monad transformers: State, ErrorT, and WriterT. This was primarily for debugging reasons: I wanted to have ErrorT to give good error messages with context, WriterT to log events for later perusal, and State was there for convenience. I called this monad stack "Er." So the first thing I wrote was something like this:<br>
<br></font></div><div><font face="courier new,monospace">-- return True if an illegal combination is found<br></font></div><font face="courier new,monospace">prune :: Music -> Er Bool<br></font></div><font face="courier new,monospace">prune music = do<br>
</font></div><font face="courier new,monospace">  flags <- forM [0..size music-1] (\ix -> checkOneNote music ix)<br></font></div><font face="courier new,monospace">  return $ or flags<br><br></font></div><font face="courier new,monospace">checkOneNote :: Music -> Int -> Er Bool<br>
</font></div><div><font face="courier new,monospace">checkOneNote music ix = do<br></font></div><div><font face="courier new,monospace">  tell $ "Checking note " ++ show ix ++ "\n"<br></font></div><div>
<font face="courier new,monospace">  -- note: were thunks created by following line left unevaluated thanks to laziness of "or flags" above?<br></font></div><div><font face="courier new,monospace">  doSomething music ix<br>
</font></div><div><font face="courier new,monospace"><br></font></div><font face="courier new,monospace">I already knew from past experience that mapM (and forM) evaluate every computation within the list so I wasn't really expecting this to be lazy, and it wasn't. Judging from what was "told" to my MonadWriter, I could see it was checking every note and not stopping early at the first illegal note.<br>
<br></font></div><font face="courier new,monospace">My first question is: by any chance was this an illusion through my use of "tell"? What I mean, is that was it leaving thunks unevaluated thanks to the "or flags" expressions lazy behavior, or would it have left them unevaluated if I hadn't had the "tell" there?<br>
<br></font></div><font face="courier new,monospace">I rewrote this using this function:<br><br></font></div><br><font face="courier new,monospace"><font face="courier new,monospace">pruneRecursive :: Music -> Int -> Int -> Er Bool<br>
</font><font face="courier new,monospace">pruneRecursive music maxIx ix <br></font><font face="courier new,monospace">  | ix == maxIx = return False<br></font><font face="courier new,monospace">  | do flag <- checkOneNote music maxIx ix<br>
</font><font face="courier new,monospace">       if flag then return True<br></font><font face="courier new,monospace">               else checkOneNote music maxIx (ix+1)<br><br></font></font></div><div><font face="courier new,monospace"><font face="courier new,monospace"><font face="courier new,monospace">According to the writer messages, this was not doing any unnecessary work. <br>
<br></font></font></font></div><div><font face="courier new,monospace"><font face="courier new,monospace"><font face="courier new,monospace">Just wondering if it was really necessary to rewrite this. What if I removed the tell messages later, or put them inside 'when' like this<br>
<br></font></font></font></div><div><font face="courier new,monospace"><font face="courier new,monospace"><font face="courier new,monospace">   when (debugFlag) (tell ..)<br><br>and then set debugFlag to False for time-critical program runs?<br>
<br></font></font></font></div><div><font face="courier new,monospace"><font face="courier new,monospace"><font face="courier new,monospace">Dennis<br><br></font></font></font></div><div><font face="courier new,monospace"><font face="courier new,monospace"><font face="courier new,monospace"><br>
</font></font></font><div><div><div><div><div><font face="courier new,monospace">    <br></font><div><div><font face="courier new,monospace"><br></font></div></div></div></div></div></div></div></div></div></div></div></div>
</div>