弗里尔 monad

有一个替代的自由 monad 公式叫做 Freer（或 Prompt，或 Operational）monad。Freer monad 不需要 Functor 实例用于其底层指令集，并且它具有比标准免费 monad 更可识别的列表式结构。

Freer monad 将程序表示为属于指令集 i :: * -> * 的原子指令序列。每条指令都使用其参数来声明其返回类型。例如，State monad 的基本指令集如下：

data StateI s a where
    Get::StateI s s  -- the Get instruction returns a value of type 's'
    Put::s -> StateI s ()  -- the Put instruction contains an 's' as an argument and returns ()

使用:>>= 构造函数对这些指令进行排序。:>>= 接受一条指令返回 a 并将其预先添加到程序的其余部分，将其返回值输入到 continuation 中。换句话说，给定返回 a 的指令，以及将 a 转换为返回 b 的程序的函数，:>>= 将生成一个返回 b 的程序。

data Freer i a where
    Return::a -> Freer i a
    (:>>=) :: i a -> (a -> Freer i b) -> Freer i b

请注意，a 在:>>= 构造函数中是存在量化的。解释器了解 a 的唯一方法是通过 GADT i 上的模式匹配。

除了 ：共同米田引理告诉我们，Freer 同构于 Free。回想一下 CoYoneda 仿函数的定义：

data CoYoneda i b where
  CoYoneda::i a -> (a -> b) -> CoYoneda i b

Freer i 相当于 Free (CoYoneda i)。如果你使用 Free 的构造函数并设置 f ~ CoYoneda i，你会得到：

Pure::a -> Free (CoYoneda i) a
Free::CoYoneda i (Free (CoYoneda i) b) -> Free (CoYonda i) b ~
        i a -> (a -> Free (CoYoneda i) b) -> Free (CoYoneda i) b

我们可以通过设置 Freer i ~ Free (CoYoneda i) 来恢复 Freer i 的构造函数。

因为 CoYoneda i 对于任何 i 都是 Functor，Freer 对于任何 i 都是 Monad，即使 i 不是 Functor。

instance Monad (Freer i) where
    return = Return
    Return x >>= f = f x
    (i :>>= g) >>= f = i :>>= fmap (>>= f) g  -- using `(->) r`'s instance of Functor, so fmap = (.)

可以通过将指令映射到某个处理程序 monad 来为 Freer 构建解释器。

foldFreer::Monad m => (forall x. i x -> m x) -> Freer i a -> m a
foldFreer eta (Return x) = return x
foldFreer eta (i :>>= f) = eta i >>= (foldFreer eta . f)

例如，我们可以使用常规 State s monad 作为处理程序来解释 Freer (StateI s) monad：

runFreerState::Freer (StateI s) a -> s -> (a, s)
runFreerState = State.runState . foldFreer toState
    where toState::StateI s a -> State s a
          toState Get = State.get
          toState (Put x) = State.put x