[Haskell-beginners] monad transformers and laziness

[Dennis Raddle]

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

g = x || y || z

will not evaluate y and z if x turns out to be true.

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:

-- return True if an illegal combination is found
prune :: Music -> Er Bool
prune music = do
  flags <- forM [0..size music-1] (\ix -> checkOneNote music ix)
  return $ or flags

checkOneNote :: Music -> Int -> Er Bool
checkOneNote music ix = do
  tell $ "Checking note " ++ show ix ++ "\n"
  -- note: were thunks created by following line left unevaluated thanks to
laziness of "or flags" above?
  doSomething music ix

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.

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?

I rewrote this using this function:


pruneRecursive :: Music -> Int -> Int -> Er Bool
pruneRecursive music maxIx ix
  | ix == maxIx = return False
  | do flag <- checkOneNote music maxIx ix
       if flag then return True
               else checkOneNote music maxIx (ix+1)

According to the writer messages, this was not doing any unnecessary work.

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

   when (debugFlag) (tell ..)

and then set debugFlag to False for time-critical program runs?

Dennis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140408/5bc16be3/attachment.html>