Monadic Function_Haskell笔记12
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 2liftM的具体实现如下：
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 >>= _ = Nothingjoin中的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) mafoldr :: 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]
55P.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
55P.S.受标准答案的启发，可以换一下参数顺序，减少一层lambda：
foldM'' acc a xs = foldr (\v ma -> ma >>= acc v) (return a) xs组合
我们知道函数可以组合：
(.) :: (b -> c) -> (a -> b) -> a -> cf . g . h就是从右向左组合，例如：
> ((+1) . (/2) . (subtract 1)) 7
4.0monadic 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的函数，组合顺序也是从右向左