弗里爾 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