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 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的函數，組合順序也是從右向左