Syntax extensions: mdo and do...rec

[Levent Erkok]

> On the necessity of rec syntax, how is a statement like
>  do rec binds1
>     rec binds2
>     stmts
> different from
>  do BV1 <- mdo binds1
>                return BV1
>     BV2 <- mdo binds2
>                return BV2
>     stmts
> where BVn is a tuple of all the variables bound in bindsn.

These two expressions are semantically different if your mfix doesn't
satisfy the right shrinking property. (Note that right shrinking is not
an assumed property for value recursion operators.) 

Examples: IO/Maybe/Strict-state/Lists and many others don't satisfy
right-shrinking. (On the other hand more "well-behaved" monads like:
Environments/Lazy State/Identity etc satisfy right-shrinking). There's a
theorem stating that (roughly) any monad based on a disjoint sum with more
than one constructor will fail this property.

The problem is that in the first expression "rec binds1" and "rec binds2"
might fail to terminate while the "mdo" forms in the second expression can
terminate due to segmentation. If your mfix satisfies right-shrinking, 
then they are provably equivalent. Note that rec means "just wrap mfix"
around these binders, while "mdo" means perform segmentation and find
minimum "rec" blocks.

This stuff is all explained in the Haskell Workshop paper, or chapter 7 of
my thesis, all available at: http://www.cse.ogi.edu/pacsoft/projects/rmb

(The thesis is more up-to-date with respect to terminology. Also the "rec"
keyword is not mentioned anywhere in those papers since that was a last
minute addition by Simon PJ inspired by Ross's arrow notation.)
        
-Levent.