Free 与 Freer Monad，将 Monad 放回柜橱

译自 Free and Freer Monads: Put Monad Back into Closet

简介

编写 Monad（现在还包括 Applicative 和 Functor）的实例，并确保实例符合 Monad 定律不但是定义 Monad 的重要部分，同时也是数量正在以指数级膨胀的「Monad 教程」的重要部分。而本文认为所有这些实例都不过是 boilerplate－－可以避免的 boilerplate！或许是因为听起来像拉丁语的名字和其引起的人们对顶尖数学的兴趣，这些琐碎的 boilerplate，琐碎的 Monad 定律，毫无新意的「管道」吸引了过多的关注。如果我们能直接思考副作用本身而非这些管道的工作原理，难道不让人耳目一新吗？

Free Monad，以及我们正要提到的 Freer Monad 将把我们从 boilerplate 中解放出来，从而专注于副作用的本质。有了它，我们就可以将解释器这一在编程语言研究和实践中的大杀器引入到副作用编程中－－为副作用定义解释器。

目前，已经有了许多关于 Free Monad 的精彩解释，这些解释往往援引了幺半群、普适代数和范畴论的观点。但最近流行的 Freer Monad 却给我们带来了困境：它的定位是什么？它能让我们更清晰地思考副作用吗？它也是『自由』的吗？如果是，为什么这些数学上的解释都没有预言 Freer Monad 的存在呢？本文接下来将解决这些问题，但唯独最后一个问题，我只能说，人们几次发现 Free Monad 都不是通过范畴论。（事后来看，范畴论上的联系确实存在，而且确实有洞见性）。与许多已有的解释不同，本文采取了通俗的方法，通过具体的例子而非抽象的代数解释 Free Monad（有关范畴论的内容将仅在括号中提及）。

经典 Monad

我们用耳熟能详的 State Monad 举例，该 Monad 代表『访问或更新一个可变状态』的副作用。常见的实现将这个可变状态作为返回值和参数沿着程序传递，然后通过 get 和 put 两个原语来获取/更新变量。

newtype State s a = State{unState :: s -> (a,s)}

get :: State s s
get = State $ \s -> (s,s)

put :: s -> State s ()
put s = State $ \_ -> ((),s)

runState :: State s a -> s -> (a,s)
runState = unState

get 和 put 操作，State s 蕴涵的定律以及解释器 runState，没有这三者，State s 就不能够作为真正的可变状态副作用计算使用。然而，为了在 Haskell 程序中方便地使用这些操作，我们要编写以下代码。

instance Functor (State s) where
    fmap f (State m) = State $ \s -> let (v,s') = m s in (f v,s')

instance Applicative (State s) where
    pure x = State $ \s -> (x,s)
    State f <*> State x = 
        State $ \s -> let (vf,s1) = f s
                          (vx,s2) = x s1
                      in (vf vx, s2)

instance Monad (State s) where
    return x = State $ \s -> (x,s)
    State m >>= k = State $ \s -> let (v,s') = m s in unState (k v) s'

太多 boilerplate！尽管 Applicative 和 Functor 的实例可以复用 Monad 实例的代码，但也要显式给出。事实上，所有这些实例（包括 Monad 的）都不过是 boilerplate。我们可以一劳永逸地定义最通用的 Monad 实例，然后我们就不必为特定的实例和其 Monad 定律烦恼。

Free Monad

Free Monad 替我们省下了这些 boilerplate。（『自由（free）』指范畴论中『遗忘（forget）』的左伴随，我们将用平易近人的语言解释其作用）目前 State s 同时是一个 Functor、Applicative 与 Monad。让我们『遗忘』掉后两个概念：假设我们已经删除了包含 State s 的 Applicative 和 Monad 实例的文件。但事实证明我们没有失去什么，得益于 Free Monad 的构造，我们仍然可以方便地在程序中使用 State s：

data Free f a where
  Pure   :: a -> Free f a
  Impure :: f (Free f a) -> Free f a

eta :: Functor f => f a -> Free f a
eta = Impure . fmap Pure

这里的类型构造器 f 必须是 Functor：这意味着如果我们有类型为 f a 的值，且我们知道如何把类型为 a 的值转换为类型为 b 的值，我们就能获得类型为 f b 的值。换言之，f 必须支持 map 操作。长话短说：f 必须为类型类 Functor 的成员。正如其类型所示，函数 eta 将任意 Functor f，转变为 Monad Free f（同时也是 Applicative 和 Functor）

instance Functor f => Functor (Free f) where
  fmap f (Pure x)   = Pure $ f x
  fmap f (Impure m) = Impure $ fmap (fmap f) m

instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure f <*> m   = fmap f m
  Impure f <*> m = Impure $ fmap (<*> m) f

instance Functor f => Monad (Free f) where
  return = Pure
  Pure a   >>= k = k a
  Impure m >>= k = Impure (fmap (>>= k) m)

对于任意 Functor f，Free f 都拥有 Monad 的性质。如果我们有 Free Monad ，那么当需要诸如可变状态或者其他副作用时，我们也不必再编写其他任何 Monad 实例。 Free Monad 满足且仅满足所有 Monad、Applicative 和 Functor 的定律，我们也不必费心去证明了。

回到刚才的例子：我们『遗忘』了 State s 是 Monad，现在我们将其重新变为 Monad。无须手动编写任意 Monad 或 Applicative 的实例，我们只需要写：

type FState s = Free (State s)

然后专注于可变状态副作用的本质：getF 与 putF 原语（可以复用刚才的 get和 put 的实现）

getF :: FState s s
getF = eta get

putF :: s -> FState s ()
putF = eta . put

以及副作用解释器

runFState :: FState s a -> s -> (a,s)
runFState (Pure x) s   = (x,s)
runFState (Impure m) s = let (m',s') = unState m s in runFState m' s'

我们就已经准备好对可变状态副作用编程了，如下示

testState :: FState Int Int
testState = do 
  putF 10
  x <- getF
  return x

test_run = runFState testState 0
-- (10,10)

重申一下，要使用可变状态副作用，我们只需要：定义 State s 以及其 Functor 实例，编写 get 和 put 以及副作用解释器 runFState。我们集中精力解决重点部分，没有因为 boilerplate 般的实例定义和相应定律而分心。我们甚至发现 Functor (State s)实例也是不必要的，在此暂时按下不表。

有利可图的『作弊』

如果仔细观察 runFState，我们可以发现这与原本的 State s Monad 的 (>>=) 实现有许多相似之处（这里鼓励读者写出 join :: State s (State s a) -> State s a 的实现以发现出更多相似点。）－－毕竟我们最终也必须实现类似于 (>>=) 的东西。这听起来像一种『作弊』，从直觉来说确实：范畴论的许多形式化构造看起来确实像作弊。Free f 不会像魔法一样自动将副作用计算 f a 与 a -> f b 结合起来，因为 f 可以为任何东西，所以它不知道如何结合。它只是把所有 (>>=) 的参数积累起来，供我们在最后集体处理。换言之，Free f 只是把具体工作从 Monad 的 (>>=) 中转移到 runFState。但 Free f 也并非毫无用处。Free Monad 会自动应用 Monad 的『单位元定律』，并将所有 (>>=) 的参数线性化后结合在一起。简而言之，Free f 如我们所愿替我们完成了许多脏活。

而更重要的是，Free f 有助于将所有处理副作用的具体工作转移给解释器，定义副作用会更简单，也更易于推理。有了 Free f，我们就可以给副作用定义解释器。此外，Free Monad 也解决了『如何组合 Monad』这自 Monad 诞生以来即困扰 Monad 的问题。

Freer Monad

在上文里，我们先『遗忘』了 State s 的 Monad 和 Applicative 实例，然后通过 Free Monad 取回了这些实例（或者说，伪造的实例）。Free Monad 免费为我们提供了我们所『遗忘』的实例。无独有偶，我们甚至可能『遗忘』State s 是 Functor，如果我们没有 fmap，Free Monad 就不起作用了。不过，我们仍可以通过『作弊』的方法来获得 fmap。譬如某结构 g 不支持 fmap，我们可以通过下面的方法来伪装其支持

data Lan g a where
  Lan :: g x -> (x -> a) -> Lan g a

instance Functor (Lan g) where
  fmap f (Lan gx h) = Lan gx (f . h)

lan :: g a -> Lan g a
lan ga = Lan ga id

（从技术角度，Lan 是『左 Kan 扩张』的一个实例）Lan g a 的 fmap 实现保存其参数，但不进行实际的映射。尽管如此，它看起来仍然像一个可映射的结构，并且提供了必要的 Functor 实例和 fmap 操作。因此 Free (Lan g) 也是 Monad。我们成功从没有任何特殊性质的 g a 得到了 Monad，这就是所谓 Freer Monad。发表在 Haskell Symposium 2015 上的论文中描述了一个可扩展的版本。对于本文，下列的 Free (Lan g) 的去语法糖的版本就足矣：

data FFree g a where
  FPure   :: a -> FFree g a
  FImpure :: g x -> (x -> FFree g a) -> FFree g a

与 Free f 不同的是，类型构造器 g :: * -> * 不必是 Functor，可以是任何东西。但 FFree g 无论如何都是 Functor、Applicative 和 Monad

instance Functor (FFree g) where
  fmap f (FPure x)     = FPure (f x)
  fmap f (FImpure u q) = FImpure u (fmap f . q)

instance Applicative (FFree g) where
  pure = FPure
  FPure f     <*> x = fmap f x
  FImpure u q <*> x = FImpure u ((<*> x) . q)

instance Monad (FFree g) where
  return = FPure
  FPure x      >>= k = k x
  FImpure u k' >>= k = FImpure u (k' >>> k)

其中

(>>>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >>> g = (>>= g) . f

是副作用函数的组合（Kleisli 组合）（已知 FFree g = Free (Lan g)，从范畴论的角度很容易发现 FFree 也符合 Monad 三定律。范畴论在这里确实有一定的闪光点：它提出的通用理论在许多特殊的情况下都适用）。因此无论一个结构 g a 是什么，我们都可以将其转变为一个 Monad：

etaF :: g a -> FFree g a
etaF fa = FImpure fa FPure

对比 Free Monad 中的 eta，etaF 不约束其参数必须为 Functor 的实例。无疑提高了我们编程的效率。

现在，要让 State s 成为 Monad，我们不需要编写 Monad 甚至 Functor 的实例了，只需要写：

type FFState s = FFree (State s)

然后定义对应的操作原语：

getFF :: FFState s s
getFF = etaF get

putFF :: s -> FFState s ()
putFF = etaF . put

最后写副作用的解释器：

runFFState :: FFState s a -> s -> (a,s)
runFFState (FPure x) s     = (x,s)
runFFState (FImpure m q) s = let (x,s') = unState m s in runFFState (q x) s'

编程可变状态副作用的所有必须工作（如 testState）便已大功告成。

这种『形式化上的作弊』，即『把具体工作从 Monad 的 (>>=) 转移到解释器 runFFState』的表现已经更加清晰。以一个典型的副作用计算 testState 为例，对 do notation 解语法糖后得到

((FImpure (put 10) Pure) >>= \_ -> getF) >>= \x -> return x

用 eff 代指副作用，k1,...,kn 代指后继的运算，可以得到其一般形式

(((FImpure eff k1) >>= k2) >>= ...) >>= kn

然后代入 FFree g 的 (>>=) 的定义得

FImpure eff (k1 >>> k2 >>> ... >>> kn)

可以看出，处理副作用 eff 的逻辑转移到了 runFFState 中，而 FFree g 只是把所有的后续运算 k1,...,kn 收集到了用 (>>>) 构造的异构列表内。（读者可能会联想到 Free Monoid 和 Free Monad 的范畴论联系，其中 Free Monoid 代表一种抽象的序列结构）

将 k1 >>> k2 >>> ... >>> kn 视为列表不仅只是有趣。Haskell 2015 论文通过将 k1 >>> k2 >>> ... >>> kn 视为真正的异构数据结构，一个高效的队列结构，从而显著提高了 Freer Monad 的性能。

回顾我们的 State s 例子，我们发现不但可以遗忘掉 return 和 (>>=)，而且还可以遗忘 fmap 操作，并且仍然能通过 FFree (State s) 重新获得 State Monad。FFree g 也是『自由』（在范畴论/普适代数的意义上）的。并且可以通过『形式化上的作弊』来恢复诸如 fmap 和 (>>=) 这些我们『遗忘』的属性。

Freer Monad 比 Free f『遗忘』的更多，boilerplate 更少，因此用它的编程效率就更高。换言之，我们不需要再手动编写 Monad 或 Functor 的实例，Freer Monad 免费提供。

副作用的定义解释器

我们已经知道，对于任意的 g，FFree g 是 Monad。在本节我们将充分利用 Freer Monad 的这一性质。在上文中，我们对可变状态这一副作用的实现仍然分布在 put、get 以及解释器 runFFState 里面。现在，我们将所有的实现汇集在一处解释器中：

data StateEff s x where
  Get :: StateEff s s
  Put :: s -> StateEff s ()

type EffState s = FFree (StateEff s)

我们用 StateEff s x 命名可变状态副作用并且定义了它的类型：有人可能会想将其成为副作用签名。尽管它不是 Functor，也没有什么特殊的性质，但 FFree (StateEff s) 仍是一个 Monad。其原语 getEff 与 putEff 的实现

getEff:: EffState s s
getEff = etaF Get

putEff:: s -> EffState s ()
putEff = etaF . Put

也不再直接访问或者更新某个可变状态了。事实上，它们什么也不做，它们只是『声明』自己想要做的事情：或访问某个可变状态，或者更新它。实现这些声明的工作转交给了解释器。

runEffState :: EffState s a -> s -> (a,s)
runEffState (FPure x) s     = (x,s)
runEffState (FImpure m q) s =
  let (x,s') = unEffState m s in runEffState (q x) s'

unEffState :: StateEff s a -> (s -> (a,s))
unEffState Get s     = (s,s)
unEffState (Put s) _ = ((),s)

现在整个副作用的具体实现都放在了解释器中。我们将其称为副作用的「定义解释器』，它赋予了「可变状态』与「访问或更新一个可变状态的操作』意义。当所有具体实现汇集于一处，我们就更容易观察或推理它如何运行，同理，也更容易改变它如何运行了－－用不同的解释器来解释同一个带有副作用的程序即可。我们可以用全局的 reference cell 来实现可变状态，也可以将其作为与另外的独立进程之间的消息交换。本文没有说明 Freer Monad 如何简化了定义副作用之间的交互，有兴趣者请参阅发布在 Haskell Symposium 2013 和 2015 上的论文及其随附的代码。

参考

Heinrich Apfelmus: The Operational Monad Tutorial

上述的副作用定义解释器的方案其实就是 Heinrich Apfelmus 提出的 Operation Monad。本文通过 Free Monad 推导，因此简单证明了其符合 Monad 定律。我们的方法与 Operation Monad 的主要不同在于可扩展性和组合 Monad 的能力，Haskell 2015 论文介绍了这一点。

性能

我们需要为 Free 和 Freer Monad 给我们带来的所有好处而付出性能代价吗？迄今为止，答案是肯定的。

但我们应该认识到，性能并非总是最重要的。很大一部分我们日常交互使用的软件都是用像 Python、Perl 或 Ruby 这样的语言编写的，而它们也称不上编程语言中的速度之王。

Haskell 2015 论文旨在改进 Free Monad 的性能（请参阅 Jaskelioff & Rivas, ICFP 2015）。优化过的 Freer Monad 在多种副作用混合的程序中表现出了良好的性能，在运行速度和内存占用指标上均优于 Monad Transformer。即便是单一副作用的程序，尤其是 State Monad（GHC 对此有良好优化），Free Monad 也可与原生的 State Monad 媲美（请参阅 Wu & Shrijvers, MPC 2015）。

结论

Free 以及 Freer Monad 改变了我们看待 Monad 的方式。Monad 实例以及 Monad 定律现在就像一些无聊的管道，该把那些 Monad 教程冲进下水道了。从这个角度看，争论 Applicative 是否为 Monad 的超类并无意义，因为我们不应该写任何 Monad 的实例。在摆脱了 Monad 实例和 Monad 定律的干扰之后，我们可以专注于副作用本身。试想，Freer Monad 将我们从 Monad 中解放（free）出来。

简介#

经典 Monad#

Free Monad#

有利可图的『作弊』#

Freer Monad#

副作用的定义解释器#

参考#

性能#

结论#

简介

经典 Monad

Free Monad

有利可图的『作弊』

Freer Monad

副作用的定义解释器

参考

性能

结论