haskell - 递归可以脱糖吗

Question

可以将递归 do 语句脱糖为一系列 >>= 语句吗？如果是这样，reverse state monad's definition for >>= 是什么意思？脱糖后的样子？

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'')

Answer 1

Recursive-do 不仅可以对一系列 >>= 调用进行脱糖，而且只要存在实际递归，就可以将其脱糖为 mfix 调用。整个递归过程是在 mfix 调用中通过技术上称为“魔法仙尘”的方式发生的。

说真的，每个 monad 的发生方式都是不同的，这就是为什么它是一个类 MonadFix 而不仅仅是一个函数。但重要的一点是，它可以“神奇地”将你自己的结果作为参数传递给你，这只是由于 Haskell 的懒惰才可能发生，因此必须小心处理。

一般来说，是这样的:

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

脱糖:

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

因此应用到反向状态定义，它看起来像这样:

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''))

从这里开始，我们可以像往常一样对常规 do 进行脱糖:

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''))

(也就是说，除非我搞砸了一些东西 - 很多蜱虫到处飞:-)