liftM

liftM :: Monad m => (a1 -> r) -> m a1 -> m r

从类型声明来看，这不就是Functor的fmap嘛：

fmap :: Functor f => (a -> b) -> f a -> f b

只是把context换成了Monad而已，此外没什么区别。并且对于遵守Functor laws和Monad laws的类型，这两个函数是完全等价的，例如：

> liftM (+1) (Just 1)
Just 2
> fmap (+1) (Just 1)
Just 2

liftM的具体实现如下：

liftM   :: (Monad m) => (a1 -> r) -> m a1 -> m r
liftM f m1              = do { x1 <- m1; return (f x1) }

等价于：

liftM' f m = m >>= \x -> return (f x)

注意，这个实现并不依赖Functor的特性，仅靠Monad具有的行为就可以完成（并且如果遵守Monad laws的话，就与fmap完全等价，仅将函数应用到具有context的值上，不做任何多余的事情），从这个角度看，Monad比Functor更强大

已经证明了Monad比Functor强，那Applicative呢？

Applicative最关键的是这个东西：

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

实际上用Monad也能实现，叫做ap：

ap :: Monad m => m (a -> b) -> m a -> m b

很容易搞定：

mf `ap'` m = do
  f <- mf
  x <- m
  return (f x)

所以，Monad还比Applicative强大。更进一步的，如果要实现自定义Monad，可以先实现return和>>=，然后就很容易实现Applicative（令<*> = ap，pure = return）和Functor（令fmap = liftM）

我们知道有liftA2（直到liftA3），用来应对“多参”函数：

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d

实际上也有对应的liftM2（直到liftM5）：

liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r

例如：

> liftM2 (+) (Just 1) (Just 1)
Just 2
> liftM3 (\x y z -> x + y + z) (Just 1) (Just 2) (Just 3)
Just 6

从fmap推及liftM，再到liftM5就很容易理解了

join

可能会面临monadic value的value还是monadic value的场景，例如：

Just (Just 1)

那么如何取出内层的monadic value呢？可以用join函数：

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

试玩一下：

> join (Just (Just 1))
Just 1
> join Nothing
Nothing
> join (Just (Just (Just 1)))
Just (Just 1)

注意，类型上要求内层和外层的Monad相同（都是m），所以join (Just [1])之类的是无法正常工作的

从上面Maybe的示例来看，join好像没什么实际意义，再看看其它Monad：

> join [[1, 2], [3], [4, 5]]
[1,2,3,4,5]
> join (writer (writer (1, "a"), "b")) :: Writer String Int
WriterT (Identity (1,"ba"))

有点join（连接）的意思了，取出内层monadic value之后似乎还做了运算。猜测是这样：

join' mm = do
  m <- mm
  m

等价于：

join'' mm = mm >>= (\m -> m)
-- 即
join'' mm = mm >>= id

那内层List是被谁连接起来的呢？因为List的>>=实现是List Comprehension：

xs >>= f             = [y | x <- xs, y <- f x]

所以在List的场景，等价于：

joinList xss = xss >>= (\xs -> xs)
joinList' xss = [y | x <- xss, y <- id x]

Writer的场景与List类似，运算都是由>>=完成的，而Maybe不带运算也是因为其>>=实现：

(Just x) >>= k      = k x
Nothing  >>= _      = Nothing

join中的k就是id，所以仅原样取出内层Maybe值

P.S.另外，一个有趣的东西：

m >>= f = join (fmap f m)

也就是说>>=等价于用转换函数（f :: a -> m b）对monadic value（m）做映射，得到一个monadic monadic value，再通过join取出内层monadic value就是最终结果：

> fmap (\x -> return (x + 1)) (Just 1) :: Maybe (Maybe Int)
Just (Just 2)
> join (Just (Just 2))
> Just 2

> Just 1 >>= (\x -> return (x + 1))
Just 2

实际上，这个等价关系提供了另一种实现>>=的思路，只要实现join就好了。这在实现自定义Monad instance的时候尤其好用，如果不知道该如何实现>>=才能保证Monad laws，不妨换个角度，考虑去实现能把嵌套的monadic value打平的join

filterM

类似于普通的filter：

filter :: (a -> Bool) -> [a] -> [a]

filterM长这样：

filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]

注意，predicate函数（a -> m Bool）的Bool返回值具有context了，这有什么作用？

允许在过滤过程中加入context，并且会被保留到结果（m [a]）中。例如：

> graterThan2 = filterM (\x -> if (x > 2) then writer (True, [show x ++ " reserved"]); else writer (False, [show x ++ " discarded"])) [9, 5, 0, 2, 1, 3] :: Writer [String] [Int]
> fst . runWriter $ graterThan2
[9,5,3]
> mapM_ putStrLn (snd . runWriter $ graterThan2)
9 reserved
5 reserved
0 discarded
2 discarded
1 discarded
3 reserved

在对List进行过滤的同时，利用Writer Monad记录了操作日志，尤其是被丢掉的元素也记下了相关信息（例如0 discarded），很有意思

还有更有趣的用法：

powerset :: [a] -> [[a]]
powerset = filterM (\x -> [True, False])

定义了一个奇怪的函数，接受一个数组，返回一个二维数组，试玩一下：

> powerset [1, 2, 3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

从作用上来看是个求幂集（集合的所有子集组成的集合，包括空集和自身）的函数，考虑一下filterM是如何做到的？

predicate函数\x -> [True, False]同时返回了多个结果：保留和丢掉。又是List的non-deterministic语境的应用：

[a]代表同时有好多结果的computation(non-deterministic computation)

non-deterministic计算能够产生多个结果，因此，对powerset场景而言，求幂集的一种有效方式是：遍历集合中的每个元素，进行两种操作（保留它和丢掉它），并把操作结果收集起来

再看filterM的实现：

filterM          :: (Applicative m) => (a -> m Bool) -> [a] -> m [a]
filterM p        = foldr (\ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x)) (pure [])

（摘自Control.Monad）

foldr遍历数组，初始值为pure []，累加函数（accumulator）是\ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x)，对当前元素用liftA2做映射，视p x的结果返回x:或id（保留的话，把当前元素插入到结果集；丢掉的话，结果集保持原状）

看起来比较迷惑，补全参数后，实际上是这样：

\ x ma -> liftA2 (\ flg a -> if flg then (x: a) else id a) (p x) ma

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b接受一个二元函数，其参数顺序是当前元素和累加结果（分别对应上面的x和ma，ma的初始值是pure []），liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c能够把一个二元函数应用到两个monadic value（分别是p x和ma）上，再返回一个monadic value。最后，这些monadic value被foldr通过mappend折叠起来得到最终结果

P.S.没错，foldr的实现用到了foldMap :: Monoid m => (a -> m) -> t a -> m，具体见Data.Foldable

foldM

foldl对应的monadic版本叫foldM：

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b

例如：

> foldl (\a x -> a + x) 0 [1..10]
55

P.S.一个小细节，foldl与foldr的累加函数的参数顺序是相反的，前者是a v，后者是v a

如果希望给foldl添上一个计算语境（比如可能会失败的语境），用foldM能够轻松搞定：

> foldM (\a x -> if (a > 99) then Nothing; else Just (a + x)) 0 [1..10]
Just 55
> foldM (\a x -> if (a > 99) then Nothing; else Just (a + x)) 0 [1..100]
Nothing

这个场景假定求和超过99的话，认为大数溢出，计算失败

猜一下foldM的实现：

foldM' acc a xs = foldl (\ma v -> ma >>= (\a -> acc a v)) (return a) xs

关键点在于维护累加值的context，参与运算（喂给acc）时去掉，遍历时添上。标准（库）答案是这样的：

foldM          = foldlM
foldlM f z0 xs = foldr f' return xs z0
  where f' x k z = f z x >>= k

等等，f z x >>= k发生了什么？

f是累加函数
z0是初始值
xs是Foldable实例
z是累加值
x是当前元素
k是？像是return，接受普通值，返回具有context的值

一步步看，其中f'的类型是：

f' :: Monad m => t -> (a -> m b) -> a -> m b

而foldr的类型是：

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

最难以捉摸的是：

(foldr f') :: (Foldable t, Monad m) => (a -> m b) -> t t1 -> a -> m b

这一步发生了什么？

如果只喂给foldr一个参数，要求是个二元函数a -> b -> b，要求第二个参数和返回值类型相同，所以应该换个姿势看f'：

f' :: Monad m => t -> (a -> m b) -> (a -> m b)

此时b相当于a -> m b，对应到foldr中：

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
--  (a -> b -> b)被f'填上了，剩下b -> t a -> b，把b替换成a -> m b
foldr f' :: Foldable t => (a -> m b) -> t a -> (a -> m b)
-- 即
(foldr f') :: (Foldable t, Monad m) => (a -> m b) -> t t1 -> a -> m b

接下来喂给它3个参数，分别是：

return :: (a -> m b)
xs :: t t1
z0 :: a

顺利返回m b

P.S.之所以能进行这样巧妙的变换，是因为Haskell函数默认的柯里化特性，只有填满参数，才返回值。所以：

f' :: Monad m => t -> (a -> m b) -> a -> m b
-- 等价于
f' :: Monad m => t -> (a -> m b) -> (a -> m b)

理解起来也很容易，f' :: Monad m => t -> (a -> m b) -> (a -> m b)接受两个参数，返回一个a -> m b的函数（之前是接受3个参数，返回一个m b值）

类似的，可以这样做：

f :: (Num b, Monad m) => b -> (t -> t1 -> m b) -> t -> t1 -> m b
f a b c d = b c d >>= \v -> return (v + a)

foldr f对应的类型为：

foldr f :: (Foldable t, Num b, Monad m) => (t1 -> t2 -> m b) -> t b -> t1 -> t2 -> m b

试玩：

> foldr f (\x y -> return (x + y)) [1..10] 0 0
55

P.S.受标准答案的启发，可以换一下参数顺序，减少一层lambda：

foldM'' acc a xs = foldr (\v ma -> ma >>= acc v) (return a) xs

组合

我们知道函数可以组合：

(.) :: (b -> c) -> (a -> b) -> a -> c

f . g . h就是从右向左组合，例如：

> ((+1) . (/2) . (subtract 1)) 7
4.0

monadic function也是function，自然也能组合（实际上之前已经见过了）

在Monad laws中有提到过一个东西，叫做Kleisli composition：

-- | Left-to-right Kleisli composition of monads.
(>=>)       :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g     = \x -> f x >>= g

(<=<)       :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(<=<)       = flip (>=>)

<=<就是.的monadic版本，作用也类似：

> Just 7 >>= (return . (+1) <=< return . (/2) <=< return . (subtract 1))
Just 4.0

用来组合一系列Monad m => a -> m a的函数，组合顺序也是从右向左