Monads as Containers and Computations

发表于 更新于 分类于 ，

Monads as Containers

Monads as Computation

Monad作为Haskell中非常核心的一个Typeclass，其概念和意义有很多种理解。本文是Haskell wiki上的两篇文章《Monads as Containers》和《Monads as Computation》的笔记。

Monad as Containers

“容器”这种理解是科普时经常采用的，也是学习过程中最早期建立的理解。这种理解和Monad的定义有关：

Monad 定义

1
2
3
4
5
6
7
class Functor f where
    fmap :: (a -> b) -> f a -> f b

class (Functor m) => Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b
    join :: m (m a) -> m a

对于任意一个Monad m，m首先要是一个Functor。

其实在Functor和Monad中间还夹着一个Applicative，不过一方面历史原因Applicative出现较晚，导致标准库并没有这种约束，另一方面学习理解Monad暂时还不需要Applicative，这二者的详细讨论放在将来。

什么是Functor？最简单直观的理解就是一个容器，f a就是里面放着类型为a的数据，容器类型为f的这么一个东西。Functor提供了一个接口fmap，其含义是将一个普通的a->b函数lift成为f a -> f b的函数，也可以认为是将容器外部的函数“包装”成了容器函数。可以看出，很多数据结构天然就是Functor。

graph LR
A[a] --> B[fmap f]--> C[b]

那什么是Monad？用“容器”的观点，就是支持更多操作的更强的容器：

  • fmap :: (a -> b) -> m a -> m b：把a -> b的函数“提升”为m a -> m b的函数
  • return :: a -> m a：就是把一个数据a包装成m a
  • join :: m (m a) -> m a：把嵌套的容器“合并”成一个，flatten

这里将join当作Monad基本操作，而没有选取(>>=)，实际上两者是等价的可以转换，不过在范畴论里join是Monad定义的一部分。 join的理解是非常关键的，注意是“合并”，并不是简单的将外层容器去掉。

graph LR
subgraph bind
    A[a] --> B>a -> m b]
    B --> C[b]
end

上面三种操作就是Monad定义的全部了，我们可以根据它们构造出更多工具。

首先是(>>=)：

1
2
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
xs >>= f = join (fmap f xs)

(>>=)英文名称叫bind，不知道应该怎么翻译。用“容器”的观点，就是将m a里面的数据a取出，放到a -> m b的函数f里。其实现就是将f升格为m a -> m (m b)，最后用join将多余的m flatten。

标准库Monad的定义是return和(>>=)，用这两个可以导出liftM和join：

1
2
3
4
5
liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f xs = xs >>= (return . f)

join :: (Monad m) => m (m a) -> m a
join xss = xss >>= id

Monad的基本定义就是这些，事实上一个定义良好的Monad还应该遵守三条单子律，不过在这里就不讨论了，放在后面Monads as Computation讨论。

Monad examples

前面提到过，对于初学者其实将Monad视作“容器”是很好理解的。但是，这种观点继续下去问题就大了，对于那些具体的Monad instance，这些“容器”是什么？

Identity a

1
2
3
4
5
6
7
8
newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)

instance Monad Identity where
    return = Identity
    (Identity a) >>= f = f a

Identity这个类型，在类型中的地位相当于id在函数中的地位，就是什么都不做，直接封装。

Maybe a

1
2
3
4
5
6
7
8
9
10
data Maybe a = Nothing | Just a

instance Functor Maybe where
    fmap _ Nothing = Nothing
    fmap f (Just a) = Just (f a)

instance Monad Maybe where
    return = Just
    Nothing >>= _ = Nothing
    (Just a) >>= f = f a

Maybe这个类型代表了可能为空的容器，空就是Nothing，否则就是Just x，相当于其他语言中的None、null的处理。

[a]

1
2
3
4
5
6
7
8
9
10
data List a = Nil | Cons a (List a)

instance Functor List where
    fmap _ Nil = Nil
    fmap f (Cons a as) = Cons (f a) (fmap f as)

instance Monad List where
    return a = Cons a Nil
    Nil >>= _ = Nil
    Cons a as >>= f = f a ++ (as >>= f)

List这个类型，代表了可能存储零个或者多个数据的容器，相当于数据结构中的单链表。

Reader r a

1
2
3
4
5
6
7
8
newtype Reader r a = Reader { runReader :: r -> a }

instance Functor (Reader r) where
    fmap f (Reader m) = Reader $ f . m

instance Monad (Reader r) where
    return x = Reader $ \r -> x
    (Reader m) >>= f = f . m

从Reader r这个类型开始，问题就变得奇怪了起来。复杂的Haskell类型，经常喜欢把一些函数封装成一个类型，这玩意儿也算是“容器”吗？它是怎么把数据a存储起来的？

Reader r是一个好的开始，毕竟这东西算是最简单的“函数封装成的类型”，用context的理解就是共享一个“只读”变量r的计算环境。但是这里我们希望能有一种“容器”视角的理解，怎么把这玩意儿看作一个容器。

关键在于这个r，我们将它看作某种index下标，将一个m :: Reader r a看作是一个以r为下标，每个格子里存放类型a的数据的巨大容器。换言之，runReader :: Reader r a -> r -> a函数就相当于lookup :: Eq a => [(a, b)] -> a -> Maybe b，其作用就是对于一个Reader容器获取某个下标里面存放的数据。

也就是说，逻辑上可以将Reader r a看作一个巨大无比的数组，当然数组的下标是有限整数，但这里的r可以是任意类型，这就是Haskell可怕的地方了，我们得到了一个无限大小的类似数组的容器，并且我们其实并没有为容器中的数据a们分配内存空间，每次需要的时候，计算即可。Reader r a的代码就相当于里面存储的数据，这就是“代码即数据”的最真切体现了吧。

State s a

1
2
3
4
5
6
7
8
9
10
newtype State s a = State {runState :: s -> (a, s)}

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

instance Monad (State s) where
    return a = State $ \s -> (a, s)
    m >>= f = State $ \s -> let (a, s') = runState m s
                                (b, t) = runState (f a) s'
                            in (b, t)

State Monad可以说是最有意思的Monad之一了，基于State Monad我们可以实现Imperative式的编程。

如果使用computation或者context的视角，理解State Monad是非常简单水到渠成的事情：

  • State s a封装了一个s -> (a, s)的函数，含义就是接受一个状态，返回结果a，和下一个状态s'
  • State s a本身是描述这个计算过程，所以每次使用它必须输入一个起始状态runState m s0
  • m >>= f的bind也就很好理解了，输入状态s，计算m得到中间结果a和新状态s'，将a送给f得到新的State Monad，将s'送给它得到最终的结果和状态。

没错，State Monad很像一台自动机，其描述了给定某个状态，是怎么转移到下一个状态的，只不过这个自动机不消耗符号，反而每次转移“吐出”一个符号，而且每个节点只有一条出边。

其实如果能够在脑海中想象出这么一张状态转移的图景，那么用“容器”的视角就很简单了。

State s a是一个巨大的容器，容器以s作为下标，里面存放了数据a和下一个节点s'。显然Reader r a是一个特殊的State s a，永远不去修改状态那么状态就是“只读”的。

现在我们去用“容器”的观点理解join就水到渠成了：

  • Reader r a：join在巨大数组mma里检索r获得一个巨大数组ma，然后对ma检索r获得a，将a放在r的位置；
  • State s a：join在巨大数组mm里面检索s获得一个巨大数组m和新的下标s'，然后在m里检索s'获得a和又一个下标t，最后将(a, t)放在下标s的位置。

其实从这两个例子也可以看出，为什么前面提到过join不是简单的将外层结构去掉，而是“合并”。

将Monad视作存储数据的容器是很简单的观点，但是这个观点抽象层次太低，而且面对复杂的类型，我们很难想象出这个容器到底是怎么存储数据的，State r a尚且能够类比成数组或者Map，面对更复杂的Parser、Cont等等就很麻烦了。

Monads as Computation

将Monad视作计算本身是更高级的抽象，就像前面说的，一个程序本身是一段代码，这段代码本身就是数据。

计算的视角

Monads通常遵循下面几个前提：

  • monadic的计算有结果：对于一个Monad M，一个类型为M t的值就是一段结果类型是t的计算；
  • 对于任意的值，存在一个计算“什么都不做”，将这个值作为结果：这就是return :: Monad m => a -> m a；
  • 对于两个计算x和y，可以将他们组成一个更大的计算x >> y：其含义是先计算x，抛弃结果，计算y，将y的结果返回；
  • 更进一步，我们允许使用前一个计算的结果来决定接下来干什么：这就是>>=，ma>>=f含义就是先计算ma，其结果a决定了接下来进行计算f a。

上面就是计算视角的Monad定义，很容易发现，计算视角有两个很重要的词语“计算”和次序“。

什么叫“计算”，计算一个m :: M a产生类型为a的结果，这个计算是指什么？

“次序”是什么，先计算x后计算y，这个先后是指什么？

需要指出的是，因为以这种方式理解Monad涉及到“计算次序”这个东西，所以很容易联想到Imperative Programming，所以误以为Monad的发明就是为了解决lazy computing的 计算次序不确定性这个问题。事实上这是完全错误的。

“计算”和“次序”这两个词语，一定要绑定到具体的Monad才有意义，换言之，不同的Monad这两个词语的含义完全不同，这也是FP的魅力，简单的改变可以使同样的句子具有完全不一样 的含义。

另一方面，的确可以使用Monad来实现Imperative那样的效果，但这是完全基于函数式和lazy computing的。Monad天然不是IO，但是IO天然是Monad。使用Monad来解 决IO是非常漂亮和自然的，IO它正好就是Monad，所以可以使用Monad的一众函数库。

Do notation

在进行下面的内容之前，先引入一个语法糖syntax-sugar：

1
2
3
4
do { x } = x
do { x ; <stmts> } = x >> do { <stmts> }
do { v <- x ; <stmts> } = x >>= \v -> do { <stmts> }
do { let <decls> ; <stmts> } = let <decls> in do { <stmts> }

这就是do notation，上面的替换发生在编译前期，ghc按照上面的规则将do转换为表达式。

有了这个语法糖，我们可以轻易的写出各种简单漂亮“命令式”风格的代码：

1
2
3
4
5
6
main = do
    putStrLn "Enter a line of text:"
    x <- getLine
    putStrLn (reverse x)

fibs = 1 : 1 : [f1 + f2 | (f1, f2) <- zip fibs (tail fibs)]

do notation确实是我见过的最漂亮的语法糖了，简单直观好用。

需要注意，虽然do notation看起来非常有“命令式”的特点，但是这并不是命令式。

1
2
3
4
5
f = do
    x <- f1
    y <- f2
    z <- f3
    return (x, y, z)

这段代码如果是命令式，就是依次进行f1, f2, f3，将结果打包返回。

但是前面一节强调过，这段代码的真实控制流取决于具体是哪一个Monad，因为do只是一个语法糖，上面代码被转换为f1 >>= \x -> f2 >>= \y -> f3 >>= \z -> return (x, y, z)，所以重点是(>>=)是怎么实现的，对于Parser、[a]，可能会发生回溯backtracking，对于更复杂的Monad，例如Cont可能发生“中途截断”（类于命令式的return），甚至可能会发生并行计算。

这里就举一个最简单的例子，List。

1
2
3
4
5
a = do
    x <- [1, 2, 3]
    y <- [4, 5]
    z <- [6]
--- a = [(1,4,6),(1,5,6),(2,4,6),(2,5,6),(3,4,6),(3,5,6)]

Monad Laws

Haskell中Monad的定义只要求return和(>>=)这两个函数，理论上我们可以写出各种各样的Monads，但是数学上的单子Monad有着更强的3条性质：

  1. return v >>= f = f v
  2. x >>= return = x
  3. (x >>= f) >>= g = x >>= (\v -> f v >>= g)

直接看数学上美感不足，我们定义(>=>)：

1
2
(>=>) :: (Monad m) => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \a -> f a >>= g

三条单子律可以写作：

  1. return >=> f = f
  2. f >=> return = f
  3. (f >=> g) >=> h = f >=> (g >=> h)

前两条说明了return什么都不做，第三条说明了monadic的计算是具有结合律的，可以任意结合，也意味着可以任意拆分为monadic的计算。

需要强调的是，ghc并不会检查这三条单子律，完全由Monad的提供者自己保证。如果你写出的Monad不满足这三条性质，可以通过编译，但是可能会在后续的计算中发生意料之外的错 误。因为如果不满足单子律，但是使用者还像一般的Monad那样对待它，结果就不可控了，尤其是第三条性质如果不满足，那么我们就不能任意拆分组合。

最简单的反例就是带有计数器的容器：

1
2
3
4
5
6
7
8
data Foo a = Foo Int a

instance Functor Foo where
    fmap f (Foo n a) = Foo (n+1) (f a)

instance Monad Foo where
    return a = Foo 1 a
    (Foo n1 a) >>= f = case f a of Foo n2 b -> Foo (n1 + n2) b

工具箱

事实上，如果将Monad视作计算，那么仅仅通过提供的return和(>>=)我们就可以实现很多复杂的控制结构，比如Control.Monad里面的各种控制函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (x:xs) = do
    v <- x
    vs <- sequence xs
    return (v:vs)

forM :: Monad m => [a] -> (a -> m b) -> m [b]
forM xs f = sequence (map f xs)

when :: (Monad m) => Bool -> m () -> m ()
when p x = if p then x else return ()

liftM :: (Monad m) -> (a -> b) -> m a -> m b
liftM f x = do
    v <- x
    return (f x)

事实上，Monad非常强大，应用非常广泛，而它也只是人们发明的一种结构，Arrow是另一个强大的结构，其功能和魔力更加强大，日后学会了再讨论。