Haskell 笔记：Monad 引论

动机

pure functions 看似完美，但却不能模拟现实世界中的诸多任务。这是由于 pure functions 是良定的映射，对于特定的输入值会返回唯一的输出。这种模式在面对如下任务时会显得苍白无力：

• 有可能失败的任务。如大多数的 IO。
• 依赖外部状态的任务。如（伪）随机数生成器。
• 非确定性任务，即对于确定的输入可能有多个输出。这种在 IP 中较为少见。
• 对外界会造成影响的任务。如大多数的写入过程。

这些问题可以用数学中的域扩充技巧来解决。

域扩充

在数学中，当定义问题的范畴不足以容纳问题的解时，我们通常会对相关的范畴进行扩充。类似的技巧同样也可以应用在这里。

假设一个不良定的函数 f: A -> B：

• 如果 f 有可能失败，我们可以将 B 扩充为 Err(B) ∪ { reasons of failures }，其中 reasons of failures 可能是对异常的描述，也可以是空值一类的东西。则 f': A -> Err(B) 是良定的映射，且与 f 行为一致。事实上，这就是 Maybe Monad 和 Either Monad。
• 如果 f 依赖于外部状态，我们定义 Pref(B) 为 从外部状态空间到 B 的映射的全体，则 f': A -> Pref(B) 为良定的映射，且行为和 f 一致。换言之，对于特定的输入 a，f'(a) 返回一个函数，其中蕴含了已知 a 时如何从各种不同状态得到结果的逻辑。事实上，这就是 State Monad。
• 如果 f 具有非确定性，我们将 B 扩充为 Power(B)，即 B 的幂集。则 f': A -> Power(B) 为良定的映射，且行为与 f 一致。事实上，这就是 List Monad。
• 如果 f 依赖于真实世界，我们将 B 扩充为 IO(B)，其中的元素为一些值域为 B 的伪函数，可能对真实世界有影响。这些伪函数已经脱离了 pure functions 的范畴，但将它们看成元素是没有问题的。如此一来 f': A -> IO(B) 为良定的映射，且行为与 f 一致。事实上，这就是 IO Monad。

以上操作都有一个共同点，即对一个不良定函数的值域做了扩充，使之变成良定函数。如果用 Haskell 语言描述，它们都有相似的型：f :: a -> m b，其中 m 为扩充规则。

一个问题随之而来：这样的新函数该怎么结合？为此我们要对相关逻辑进行抽象。这就是 Monad。

Monad

这里我们尝试从实际需求出发，导出一个 Type Constructor 成为 Monad 的必要条件。

约定两个名称：

• 称 a -> m b 型函数为 monadic function
• 称 a -> b 型函数为 non-monadic function

首先需要解决的是 monadic functions 如何结合的问题。这个问题具有重要的现实意义。monadic function 常常代表某种计算任务，它们之间的结合相当于把若干计算任务串行化，而后者是非常常见的需求。

我们希望有一种运算符有如下的类型 (b -> m c) -> (a -> m b) -> (a -> m c)，在此记为 >=> （因其形状，常被叫做 fish operator）。一个自然的想法是，Monad m 需要某种平凡的拆箱操作 extract' :: m a -> a。所谓“平凡”，即 extract' 不应该丢失参数的任何信息。但这往往不能实现，因为 m a 通常会比 a 包含更多的信息，导致 extract' 无法构成良定的映射。例如 Maybe a 中的值 Nothing 就无法在 a 中找到对应的值。

而事实上，我们不需要条件这么强的拆箱操作。在 m 已是 Functor 的情况下，拆箱操作可以弱化为 join :: m (m a) -> m a。我们尝试用 fmap、 join 合成 >=>。

f :: b -> m c
g :: a -> m b

fmap f :: m b -> m (m c)
(fmap f) . g :: a -> m (m c)
join . (fmap f) . g :: a -> m c

-- i.e. 

f >=> g = join . (fmap f) . g

Functor 的假设是容易成立的。当然我们可以定义多个不同的 fmap，如此产生的 Monad 会有不同的语义。join 的假设也是容易成立的，m (m a) 通常和 m a 包含相同多的信息。故此做法是实际可行的。

我们再考虑 monadic function 和 non-monadic function 结合的问题。期望有如此一个运算：>.> :: (b -> c) -> (a -> m b) -> (a -> m c)。注意，此处返回值是 a -> m c 而不是 a -> c，因为我们不希望 a -> m b 产生的额外信息有所丢失。自然地，我们希望有一个平凡的装箱操作，return :: a -> m a。如此一来便可结合 >=> 完成上面的运算：

f :: b -> c
g :: a -> m b

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

-- i.e.

f >.> g :: (return . f) >=> g

non-monadic function 和 monadic function 另一个方向的结合是平凡的。

综上我们可以得到成为 Monad 的基本条件：

• 是 Functor，存在 fmap :: (a -> b) -> m a -> m b
• 有一个平凡的拆箱操作 join :: m (m a) -> m a
• 有一个平凡的装箱操作 return :: a -> m a

为了描述平凡，我们要求三个函数必须满足如下公理（下面的 f 为 non-monadic function）：

1. return . f == (fmap f) . return （return 的平凡性）
2. join . fmap (fmap f) == (fmap f) . join （join 的平凡性）

事实上在 Category Theory 中，还有另外两条公理：

• join . (fmap join) == join . join
• join . fmap return == join . return == id

以上四条公理描述了 Id（恒等 Functor）、m、m^2、m^3 之间的泛性质，并使图交换。

Monad Typeclass

以下为 Prelude 中的定义：

class Functor m => m a where

    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

此处没有出现 join，也没有 fish operator，而是使用了一个更常用的算符 >>= （通常称为 bind operator）。这是因为在实际中我们不直接将函数结合，而是使用 non-pointfree 的写法。

此外，还有 >> :: m a -> m b -> m b 运算符。return、>>=、>> 三者是构成 do-notation 的基础。此处不再赘述。

References

• Haskell/Category Theory
• Why Do Monads Matter?