当我们谈论Monad的时候（二）

2020/06 27

Welcome to Haskell

在上一篇文章中，我通过几个Java的例子简单的说明了Monad的本质和一些工程中常见的用途。接下来的文章就不再侧重于工程了，而是要慢慢向理论转换。而作为过渡，我选择了Haskell来代替Java进行说明。本篇文章默认读者已经对Haskell的基本语法有所了解，因此对此类内容我不会再做赘述。

我们先来改写之前的Monad：Optional和List。先来看Optional，由于它只有两种“状态”，因此在Haskell中可以这么表示

data Optional a = Value a | Empty 
    deriving Show

然后我们来实现它的fmap函数

omap :: (a -> b) -> Optional a -> Optional b
omap f (Value a) = Value (f a)
omap f Empty     = Empty

omap (+3) (Value 4)
-- Value 7

对于列表的实现也是类似的。不过由于列表可以是任意长的，因此需要定义一个链状的结构

data List a = Nil | Cons a (List a)

infixr 5 `Cons`

在Haskell中，用`包裹的函数可以作为中缀函数使用（比如加法等等），而infixr规定了`Cons`是右结合的。所以对于列表[ 1, 2, 3 ]，用List表示就是1 `Cons` 2 `Cons` 3 `Cons` Nil，等同于Cons 1 (Cons 2 (Cons 3 Nil))。如果你还是无法理解这个列表，不妨把这种形式想象成链表：Cons的第一个参数就是当前结点的值，第二个参数就是下一个结点；列表的最后总是连接尾结点Nil。

对于列表，fmap的作用就是遍历每一个列表元素，并对它们应用传入的函数f。通过模式匹配和递归，不难写出对应的lmap

lmap :: (a -> b) -> List a -> List b
lmap _ Nil = Nil
lmap f (Cons x xs) = f x `Cons` lmap f xs

为了便于调试，可以给List实现Show，这样就可以打印出比较可读的列表了。

ljoin :: String -> List String -> String
ljoin _ Nil = ""
ljoin _ (Cons x Nil) = x
ljoin mid (Cons x xs) = x ++ mid ++ ljoin mid xs

instance (Show a) => Show (List a) where
    show Nil = "[]"
    show xs = "[ " ++ ljoin ", " (lmap show xs) ++ " ]"

1 `Cons` 2 `Cons` Nil
-- [ 1, 2 ]

Functor的实现

Haskell使用Typeclass来描述Functor，对应于Java中的接口，不过表达能力要更强。标准库对Functor的定义如下：

class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b

没有具体定义的fmap就是我们需要实现的函数。使用instance可以将之前声明的Optional定义为Functor。

instance Functor Optional where
    fmap = omap

同样，列表也可以这样声明为Functor

instance Functor List where
    fmap = lmap

Applicative

但是我们没法直接声明Monad的instance，因为在Haskell中，Functor与Monad之间还有一个Applicative。那么Appliacative是什么呢？Applicative是对“应用”的抽象，它允许在容器中“存放”一个函数。

还是用例子来说明。上一篇文章的最后，我举了一个多参函数的例子。当时我们封装了一个函数liftM2用来处理2参数的函数。但是如果按照这个方法，我们对每一个数量的参数都需要写一个liftM*函数，非常麻烦。而对于容器外面的普通函数，我们就不会遇到这个问题，因为函数都是柯里化的。所以，为什么不把柯里化引入Functor呢？换言之，就是要允许在Functor中“存放”函数，而这个Functor就是Applicative。

为了把函数放进Functor，我们需要考察函数的性质。对于函数来说，最重要的就是“应用”。因此，Applicative有别于Functor的重要一点就是要求实现表达“应用”的函数。Haskell是这么表达这个函数的

(<*>) :: f (a -> b) -> f a -> f b

好吧，它的名字确实有一点怪。Haskell中全符号的、被小括号包裹的函数默认是中缀的，比如这个函数的调用就是中缀形式f <*> xs。<*>接受一个容器内的函数和值，并将运算之后的结果重新放在容器中。比如

(Value (+3)) <*> Value 2
-- Value 5

同样，柯里化的操作也是OK的

(Value (*)) <*> Value 2 <*> Value 3
-- Value 6

此外，为了将函数“装”进容器，还需要一个包装函数的函数。在Haskell中是这么表示的

pure :: a -> f a

因此就可以如此表示了

pure (*) <*> Value 2 <*> Value 3

总结一下，就可以得到Haskell对Applicative的定义了

class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

实现Applicative

实现Applicative的方法和fmap大同小异，唯一的区别就是还需要对函数进行模式匹配。

instance Applicative Optional where
    pure = Value
    
    Empty     <*> _         = Empty
    _         <*> Empty     = Empty
    (Value f) <*> (Value x) = Value (f x)

对于Optional，pure的实现就是构造函数Value。而<*>就是对函数与值都进行模式匹配，在有值的情况下将值应用给函数。

对于列表来说，情况可能稍微复杂一点。因为<*>的参数可能是多个函数和多个值。因此我们可以遍历所有可能的函数-值组合，因此我们只需要两次lmap。比如对于给定的函数列表fx与值列表xs，lmap (`lmap` xs) fx先遍历fx再遍历xs。但是它还有一个问题

fx = (+1) `Cons` (*2) `Cons` Nil
xs = 1 `Cons` 2 `Cons` Nil
lmap (`lmap` xs) fx
-- [ [ 2, 3 ], [ 2, 4 ] ]

两次lmap的结果，使结果变成了List (List Integer)，而<*>应该返回的是List Integer。因此我们还需要再设计一个join函数，来将结果转化为List Integer。对于List，这个函数通常叫concat

lappend :: List a -> List a -> List a
lappend Nil ys = ys
lappend (Cons x xs) ys = Cons x (lappend xs ys)

lconcat :: List (List a) -> List a
lconcat Nil = Nil
lconcat (Cons x xs) = lappend x (lconcat xs)

因此，我们就能完整实现List的Applicative示例了

instance Applicative List where
    pure x = x `Cons` Nil    
    fx <*> xs = lconcat $ lmap (`lmap` xs) fx

实现Monad

在Haskell中，Monad是采用上一篇中提到的flatMap形式定义的

class Applicative m => Monad m where
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b

>>=就是flatMap函数。它的行为就是取第一个参数m a的值，将其应用在第二个参数的函数（这个函数也叫monadic map）。由于这个函数并不是在容器中的，因此>>=的实现比起Applicative要更容易些。对于Optional，我们只需要对m a进行模式匹配

instance Monad Optional where
    (Value val) >>= f = f val
    Empty       >>= _ = Empty

对于列表，我们也只需要遍历一次了。

instance Monad List where
    xs >>= f = lconcat $ lmap f xs

至此，我们就在Haskell中完成了Monad的实现。

Do-notation

Do表记（do-notation）是Haskell给Monad操作提供的语法糖。在不使用Do表记情况下，使用Monad的代码是相当混乱的。比如

list1 :: List Integer
list1 = 1 `Cons` 2 `Cons` Nil

list2 :: List Integer
list2 = 3 `Cons` 4 `Cons` Nil

result = list1 >>=
  \x -> list2 >>=
  \y -> let z = x + y in
    if odd z then return (x, y) else Nil
-- reuslt = [ (1,4), (2,3) ]

这段代码计算两个列表所有数字和为奇数的取法。但是这段代码的可读性实在有限，>>=之后使用λ函数的语法是相当反直觉的，和一般编程语言中“赋值”的书写方向完全相反。而在Do表记下，这段代码可以修改为

result = do
    x <- list1
    y <- list2
    let z = x + y
    if odd z then
      return (x, y)
    else
      Nil

写出来的代码就十分清爽了，颇有命令式语言的味道。在IO操作中，这个优势还可以变得更加的明显。Haskell采用Monad实现IO相关的API，这个Monad就称为IO Monad。通过Do表记可以写出很多符合直觉的代码，比如

main :: IO ()
main = do
  putStrLn "Hello"
  putStr "Plz enter your name: "
  hFlush stdout
  input <- getLine
  putStrLn $ "Hi " ++ input

-- Hello
-- Plz enter your name: KAAAsS
-- Hi KAAAsS

不过这段代码和之前有一个不同。Haskell中的IO函数都会返回一个IO Monad，而上面的代码中，我们并没有对每一条都使用之前的结果。对于部分IO Monad（如putStrLn返回的），我们直接就抛弃了这些返回值。因此如果把语法糖展开，这段代码将会变成这样

main = 
  putStrLn "Hello" 
  >>= \_ -> putStr "Plz enter your name: "
  >>= \_ -> hFlush stdout
  >>= \_ -> getLine
  >>= \input -> putStrLn $ "Hi " ++ input

为了防止这种无意义的λ参数频繁出现，因此Haskell中还提供了丢弃上个结果的>>函数，它的实现是这样的

(>>)        :: forall a b. m a -> m b -> m b
m >> k = m >>= \_ -> k

因此这段代码可以改写为

main =
  putStrLn "Hello" >>
  putStr "Plz enter your name: " >>
  hFlush stdout >>
  getLine >>= \ input ->
    putStrLn $ "Hi " ++ input

再论Applicative

不知道你在实现和使用Monad的时候有没有发现，Monad好像几乎不怎么依赖于Applicative的实现。事实上，在Monad定义中直接使用Applicative的地方只有return函数

class Applicative m => Monad m where
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b

    m >> k = m >>= \_ -> k

    return      :: a -> m a
    return      = pure

那Haskell为什么要规定必须先实现Applicative才能实现Monad呢？这其实是一个历史问题，而且只有GHC版本在7.10之后才有这个要求。虽然Monad本身在1996年就由Philip Wadler提议加入Haskell，但是Applicative其实是2007年于Functional Pearl: applicative programming with effects提出的，因此Applicative引入Haskell的时间其实要远远晚于Monad。而由于要保持兼容性，所以在很长一段时间内Applicative与Monad的定义都是不相干的。这个不仅仅表现在它们Typeclass的定义上，在很多标准库函数上也出现了“分歧”。包括：

return（Monad）和pure（Applicative）函数实际上是一致的
>>（Monad）和*>（Applicative）实际上是一致的
liftM、liftA和fmap是一致的
liftM*（如liftM2）和liftA*（如liftA2）是一致的
<*>和ap是一致的
Traversable实际上只要求Applicative，但是实现上却要求Monad

这么多明明相同的东西却有那么多不同的表示方法（甚至写的烂的话，它们的行为还会不同），可想而知这会给编码造成多大的混乱。因此在2014年，Haskell社区提出了AMP将这些问题都做了统一，之后由GHC 7.10对相关提议做出了实现。

不过，这也只解释了为什么如今Haskell的Applicative和Monad是这种状态。那么，是什么原因使Haskell冒着把标准库搞乱的风险也要引入Applicative呢？

引入Applicative的意义

上下文无关

引入Applicative的意义有很多，其中一点就是，Applicative和Monad的侧重点不同。Applicative和Monad都能实现运算的组合与排序，因此它们都能对运算进行建模，但是Applicative在运算的过程中并没有上下文。

上下文指的就是之前产生的运算结果，也就是Do表记中的类似“变量”的东西。而没了上下文，这就意味着Applicative失去了根据之前运算结果进行下一步运算的能力。在调用形式上看，>>=的左侧是之前的运算结果，而右侧通过λ参数将这个结果引入了进来，以供之后使用。但是<*>的左侧与右侧并没有联系，因此之后的运算是无法依赖于之前的运算的。

比如对于列表推导式[ x + y | x <- [1..3], y <- [1..x] ]，它计算y的时候需要就需要先对x进行计算。因此使用Applicative是没有办法表达的

(+) <$> [1..3] <*> [1..x]
-- error: Variable not in scope: x

而Monad是可以完成这个计算的，在形式上，这个x是由λ函数的参数引入的

[1..3]
    >>= \x -> [1..x]
    >>= \y -> return (x + y)

不过这个例子并不能完全说明“不能用之前的计算结果”，或者“之前的计算结果无法影响之后的计算”。为了更好的理解Applicative运算是固定不变的，我们再举一个实现if的例子

ifA :: Applicative f => f Bool -> f a -> f a -> f a
ifA t c a = g <$> t <*> c <*> a
    where g b x y = if b then x else y

ifA (Value True) (Value 666) (Value 233)
-- Value 666
ifA (Value False) (Value 666) (Value 233)
-- Value 233

这么看起来似乎第一个Optional Bool真的能影响之后的计算流程？但是实际上，无论Optional Bool是真是假，这个ifA的计算流程都是不会改变的，看这个例子

ifA (Value True) (Value 666) Empty
-- Empty
ifA (Value False) (Value 666) Empty
-- Empty

回想Optional关于<*>的实现，就不难理解结果为什么是Empty了。而使用Monad，则可以解决这个问题

ifM :: Monad m => m Bool -> m a -> m a -> m a
ifM mbool th el = do
  bool <- mbool
  if bool then th else el

ifM (Value True) (Value 666) Empty
-- Value 666
ifM (Value False) (Value 666) Empty
-- Empty

从这个例子不难看出，Applicative的计算流程是固定的，它没有执行计算的“上下文”。而Monad的计算流程是可变的，这也意味着它的计算有“上下文”。一般的计算场景中都是有上下文的，比如IO运算。但是这种没有依赖的计算场景其实也是存在的，比如并发、Parser。试想这个场景

(\a b -> merge a b) <$> doTaskA <*> doTaskB

由于doTaskA与doTaskB不存在依赖关系，因此可以并行的对其进行计算（或者说，可以用来表示并行的计算任务）。

特例

此外，Applicative是一个比Monad更初级的结构。因此毫无疑问，存在是Applicative但不是Monad的情况。而对Applicative的刻画增强了Haskell的表达能力，比如Traversable其实只需要Applicative就可以实现了。这里举一个是Applicative但不是Monad的例子：ZipList。我们之前实现的List在处理多参数时会遍历所有可能组合（笛卡尔积），而ZipList更贴近使用习惯，它会按照同一个位置的元素来遍历多个列表。ZipList的定义本质上就是List

newtype ZipList a = ZipList { getZipList :: List a }
                  deriving Show

instance Functor ZipList where
  fmap f (ZipList xs) = ZipList $ lmap f xs

之后我们来实现Applicative。这里用到了一个技巧，Haskell的Applicative实际上是很灵活的，它允许我们在声明时选择<*>或liftA2进行声明。liftA2的作用就是上一篇中提到的liftM2。

class Functor f => Applicative f where
    {-# MINIMAL pure, ((<*>) | liftA2) #-}

    pure :: a -> f a

    (<*>) :: f (a -> b) -> f a -> f b
    (<*>) = liftA2 id

    liftA2 :: (a -> b -> c) -> f a -> f b -> f c
    liftA2 f x = (<*>) (fmap f x)

    (*>) :: f a -> f b -> f b
    a1 *> a2 = (id <$ a1) <*> a2

    (<*) :: f a -> f b -> f a
    (<*) = liftA2 const

MINIMAL注释就是用来说明这一点。由于“按位置遍历”的操作用liftA2很容易就能表达，因此我们可以直接使用liftA2来定义。

repeatList :: a -> List a
repeatList x = xs
  where xs = x `Cons` xs

zipListWith :: (a -> b -> c) -> List a -> List b -> List c
zipListWith f Nil           _             = Nil
zipListWith f _             Nil           = Nil
zipListWith f (x `Cons` xs) (y `Cons` ys) = f x y `Cons` zipListWith f xs ys

instance Applicative ZipList where
    pure x = ZipList (repeatList x)
    liftA2 f (ZipList xs) (ZipList ys) = ZipList (zipListWith f xs ys)

简单测试一下

import Data.Semigroup

incList :: Integer -> List Integer
incList i = i `Cons` incList (i + 1)

a = ZipList ('a' `Cons` 'b' `Cons` 'c' `Cons` 'd' `Cons` Nil)
b = ZipList ('5' `Cons` '6' `Cons` '7' `Cons` Nil)
c = ZipList (incList 1)

(\a b -> (a, b)) <$> a <*> b
-- ZipList {getZipList = [ ('a','5'), ('b','6'), ('c','7') ]}
(\a b c -> stimes c [a, b]) <$> a <*> b <*> c
-- ZipList {getZipList = [ "a5", "b6b6", "c7c7c7" ]}

可以看到，ZipList的行为和List是有很大区别的。而且ZipList实际上是没有合法的Monad实现的。这里的合法不是说你实现Monad会报错，而是说你写的任意Monad都不符合Monad必须符合的定律。至于这个定律是什么，在讲原理的文章中我会详细说明。

Monad的三种定义

之前提到了AMP更改了Monad的定义，而在AMP真正实现之前，Monad的定义是这样的

class Monad m where
    return :: a -> m a
    
    (>>=) :: m a -> (a -> m b) -> m b
    
    (>>) :: m a -> m b -> m b
    m >> n = m >>= \_ -> n
    
    fail :: String -> m a

而这个定义已经是Monad的完备定义了。引入AMP后，由于return已经被Applicative的pure实现，因此只需要实现>>=。

class Applicative m => Monad m where
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b

    m >> k = m >>= \_ -> k

    return      :: a -> m a
    return      = pure

不过上一篇文章中提到，通过join也可以定义Monad。而且在范畴论中，Monad也是这么定义的。所以实际上这个定义也可以定义一个Monad

class Applicative m => Monad m where
    join :: m (m a) -> m a

后记

这篇文章其实已经远远超出我预计的篇幅了。就这些内容能写这么多，我是没有想到的。原本这篇文章是想简单讲讲Monad的实现，之后再写点Haskell中常见的Monad的。但是由于上一篇文章的Applicative拖到了这篇，导致可以讲的内容大大增加。所以最终这篇文章就变成几乎纯实现Monad的介绍了，而关于Monad的应用、副作用等等的话题就要另开一篇了。不过这样的好处是，我在下一篇可以讲更多有意思的Monad了，说不定还能讲讲Arrow Type和Monad，为更后面的范畴论做些预备。

Reference

Prelude – Hackage（http://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html）
Brent Yorgey, The Typeclassopedia
Applicative Programming with Effects（http://www.staff.city.ac.uk/~ross/papers/Applicative.html）
Functor-Applicative-Monad Proposal（https://wiki.haskell.org/Functor-Applicative-Monad_Proposal）
Difference between Monad and Applicative in Haskell（https://stackoverflow.com/questions/23342184/difference-between-monad-and-applicative-in-haskell）

分享到

KAAAsS

喜欢二次元的程序员，喜欢发发教程，或者偶尔开坑。（←然而并不打算填）

KAAAsS's blog

技术宅，喜欢二次元

当我们谈论Monad的时候（二）

Welcome to Haskell

Functor的实现

Applicative

实现Applicative

实现Monad

Do-notation

再论Applicative

引入Applicative的意义

上下文无关

特例

Monad的三种定义

后记

Reference

KAAAsS

相关日志

评论

KAAAsS

Notification

Recommended Posts

Friends