递归可以脱糖吗

Question

一个递归语句可以被分解为一系列>>=语句吗？如果是这样，当它被脱糖时，反向状态 monad 的定义是>>=什么样的？

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 desugars 不仅可以对一系列>>=调用进行脱糖，而且只要确实存在递归，就可以进行一次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''))

（也就是说，除非我搞砸了 - 很多蜱虫飞来飞去:-)