CODEWITHSUNDEEP
haskellrecursion
Sledge
Sledge

Reputation: 178

Can Recursive-Do Be Desugared

Can a recursive-do statement be desugared to a series of >>= statements? If so, what does the reverse state monad's definition for >>= look like when it's desugared?

instance MonadFix m => Monad (StateT s m) where
  return x = ...
  m >>= f = StateT $ \s -> do
    rec
      (x, s'') <- runStateT m s'
      (x', s') <- runStateT (f x) s
    return (x', s'')

Upvotes: 2

Views: 154

Answers (1)

Fyodor Soikin
Fyodor Soikin

Reputation: 80805

Recursive-do desugars not only to a series of >>= calls, but also, as long as there is actually recursion, into an mfix call. It is in the mfix call that the whole recursiveness happens, via what is technically termed "magic fairy dust".

Seriously though, how it happens is different for every monad, and that's why it's a class MonadFix rather than just a function. But the important point is that it can "magically" pass you your own result as a parameter, which is only possible due to Haskell's laziness, and therefore must be handled with care.

In general, something like this:

do
    rec 
        x <- f y
        y <- g x
    return $ h x y

Desugars into this:

mfix (\ ~(x, y) -> do
    x' <- f y
    y' <- g x'
    return (x', y')
)
>>= (\(x, y) -> h x y)

So applying to the reverse state definition, it would look like this:

m >>= f = StateT $ \s ->
  mfix (\ ~((x, s''), (x',s')) -> do
    (x0, s0'') <- runStateT m s'
    (x0', s0') <- runStateT (f x0) s
    return ((x0, s0''), (x0', x0'))
  )
  >>= (\(x, s''), (x',s') -> return (x', s''))

And from here, we can just desugar the regular do as usual:

m >>= f = StateT $ \s ->
  mfix (\ ~((x, s''), (x',s')) ->
    runStateT m s' >>= \(x0, s0'') ->
    runStateT (f x0) s >>= \(x0', s0') ->
    return ((x0, s0''), (x0', x0'))
  )
  >>= (\(x, s''), (x',s') -> return (x', s''))

(that is, unless I messed up something - a lot of ticks flying around :-)

Upvotes: 5

Related Questions