时间戳

首页 > 解决方案 > 可以递归做脱糖吗

haskell - 可以递归做脱糖吗

问题描述

可以将递归执行语句脱糖为一系列>>=语句吗？如果是这样，当它被脱糖时，反向状态单子的定义是>>=什么样的？

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

标签： haskellrecursion

解决方案

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

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

推荐阅读