List Monad

在講 list monad 前我們先回憶一下 applicatives，我們知道 <*> 是可以把一個在 context 裡的 function apply 到一個 context 的值。

(+) <$> [1,2,3] <*> pure 2 -- [3,4,5]

這邊我們用了 pure 2 讓 2 有了 context，那如果今天我們把 pure 2 換成另外一個 list 呢？

(*) <$> [1,2,3] <*> [4,5,6] -- [4,5,6,8,10,12,12,15,18]

會發現我們產生了一個兩個陣列的所有元素逐一相乘的結果，這種情況我們可以用 non-deterministic 來說明，白話來說 2 是 deterministic 它只有一種可能性就是 2 ，所以 [4,5,6] 我們可以說它同時具有好幾種值的結果。

如果說 Maybe 在實作 Monad 時是想讓可能會失敗的值在 context 中，那 list 就是想處理 non-deterministic 的問題。

instance Monad [] where  
    return x = [x]  
    xs >>= f = concat (map f xs)  
    fail _ = []

基本上 return 就跟 pure 一樣就是幫我們把 x wrap [] 這個 context ，然後 >>= 就是 map 一個 list 讓他的元素逐一 apply f 然後回傳新的 list 後再 concat

之前可能沒特別提過 concat 總而言之可以想成其他語言中 flat 之類來實現 flatten 的語法，
所以 concat [[1],[2],[3]] == [1,2,3]

那為什麼會需要 concat ？還記得 >≥ 的參數嗎，其中一個就是 a → mb 意即我們會回傳一個 monadic 的 value 在 list Monad 就會是回傳一個 b of list ，那 map 本身也還是回傳一個 list ，所以 map f xs 是回傳二維陣列 （如果本來是一維陣列就是回傳二維），所以加上一個 concat 就有可以只回傳一維陣列了。

就像是有些語言有提供的 flatMap 之類的語法。

如果把上面的例子硬要用 monad 的形式來寫會是長這樣

[1,2,3] >>= \x -> (*x) <$> [4,5,6]

當然這種例子要用哪種風格的寫法完全是看個人喜好，但如果要我二選一我可能會傾向使用 applicatives style。

接下來我們來看一下其他用法

[1,2,3] >>= \x -> [x,-x] 
-- [1,-1,2,-2,3,-3]
[1,2,3] >>= \x -> [x+1,x+3] >>= \y -> [y*3]
-- [6,12,9,15,12,18]
[1,2,3] >>= \x -> [(x,'a'),(x,'b')]
-- [(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

listMonad :: [(Int,Char)]
listMonad = do
	a <- [1,2,3]
	b <- ['a','b']
	return (a,b)

-- [(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

我們可以藉由 >>= 一直串接各種計算然後最後回傳一個 list ，然後當然我們也可以用 do 來簡化 >≥ 及 lamda 的出現，這些操作是不是跟之前提到的 List Comprehension 很像？

沒錯 List Comprehension 就只是一個語法糖而已

[(a,b) | a<-[1,2,3] , b<- ['a','b']]
-- [(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

除此之外我們也可以利用 list monad 來過濾一些東西，首先先來看一下 guard function ，簡單來說它接收一個 Bool 如果為 True 就產生一個包在 context 的 () 如果 False 就是產生一個沒有值的 context。

import Control.Monad (guard)

listMonad' :: [(Int,Char)]
listMonad' = do
	a <- [1,2,3]
	b <- ['a','b']
	guard(a == 2 || b =='a')
	return (a,b)

-- [(1,'a'),(2,'a'),(2,'b'),(3,'a')]

我們可以利用 guard 來幫我們在計算 non-deterministic 的值時進行過濾。

那當然這又跟 List Comprehension 一樣了

[(a,b) | a<-[1,2,3] , b<- ['a','b'], a == 2 || b =='a']
-- [(1,'a'),(2,'a'),(2,'b'),(3,'a')]

總結來說，要使用 Applicatives 或者 List Comprehension 又或者 Monad 我覺得就看遇到的問題及個人喜好了。但只要知道 Monad 提供了類似 flatMap 的這種行為讓我們更靈活的串接各種操作那就足夠了。

今天的程式碼：

https://github.com/toddLiao469469/30days-for-haskell