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对于列表的实现也是类似的。不过由于列表可以是任意长的，因此需要定义一个链状的结构
代码语言：javascript复制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的定义如下：
代码语言：javascript复制class Functor f where
fmap :: (a -> b) -> f a -> f b没有具体定义的fmap就是我们需要实现的函数。使用instance可以将之前声明的Optional定义为Functor。
instance Functor Optional where
fmap = omap同样，列表也可以这样声明为Functor
代码语言：javascript复制instance Functor List where
fmap = lmapApplicative
但是我们没法直接声明Monad的instance，因为在Haskell中，Functor与Monad之间还有一个Applicative。那么Appliacative是什么呢？Applicative是对“应用”的抽象，它允许在容器中“存放”一个函数。
还是用例子来说明。上一篇文章的最后，我举了一个多参函数的例子。当时我们封装了一个函数liftM2用来处理2参数的函数。但是如果按照这个方法，我们对每一个数量的参数都需要写一个liftM*函数，非常麻烦。而对于容器外面的普通函数，我们就不会遇到这个问题，因为函数都是柯里化的。所以，为什么不把柯里化引入Functor呢？换言之，就是要允许在Functor中“存放”函数，而这个Functor就是Applicative。
为了把函数放进Functor，我们需要考察函数的性质。对于函数来说，最重要的就是“应用”。因此，Applicative有别于Functor的重要一点就是要求实现表达“应用”的函数。Haskell是这么表达这个函数的
代码语言：javascript复制(<*>) :: f (a -> b) -> f a -> f b好吧，它的名字确实有一点怪。Haskell中全符号的、被小括号包裹的函数默认是中缀的，比如这个函数的调用就是中缀形式f <*> xs。<*>接受一个容器内的函数和值，并将运算之后的结果重新放在容器中。比如
(Value ( 3)) <*> Value 2
-- Value 5同样，柯里化的操作也是OK的
代码语言：javascript复制(Value (*)) <*> Value 2 <*> Value 3
-- Value 6此外，为了将函数“装”进容器，还需要一个包装函数的函数。在Haskell中是这么表示的
代码语言：javascript复制pure :: a -> f a因此就可以如此表示了
代码语言：javascript复制pure (*) <*> Value 2 <*> Value 3总结一下，就可以得到Haskell对Applicative的定义了
代码语言：javascript复制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对于列表，我们也只需要遍历一次了。
代码语言：javascript复制instance Monad List where
xs >>= f = lconcat $ lmap f xs至此，我们就在Haskell中完成了Monad的实现。
Do-notation
Do表记（do-notation）是Haskell给Monad操作提供的语法糖。在不使用Do表记情况下，使用Monad的代码是相当混乱的。比如
代码语言：javascript复制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因此这段代码可以改写为
代码语言：javascript复制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。试想这个场景
代码语言：javascript复制(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 constMINIMAL注释就是用来说明这一点。由于“按位置遍历”的操作用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)简单测试一下
代码语言：javascript复制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的定义是这样的
代码语言：javascript复制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）
