combinations, list monad and list comprehension

日前 Edward 問了我一個問題，說假設有一個 list of lists,
長度不定，裡面的 list 也是長度不定。現在需要從所有的 list 中，
各挑一個 element 出來，將所有的組合變成一個 list, 該怎麼做？
例如輸入：

'((A B C) (D E) (F G H))

就會得到：

'((A D F) (A D G) (A D H) (A E F) (A E G) (A E H)
(B D F) (B D G) (B D H) (B E F) (B E G) (B E H)
(C D F) (C D G) (C D H) (C E F) (C E G) (C E H))

最直觀的作法，其實就是類似這樣...

for i in xs
for j in ys
for k in zs
for ...

也就是一個 n 層的迴圈，n 是 list of lists 的長度。說到這個，
就會想到大學時教演算法的老師說，他覺得遞迴跟迴圈不能互相取代，
例如這種狀況，很明顯是某種遞迴，要怎麼用迴圈寫呢？

很明顯這是錯的，考慮最極端的例子，大可用迴圈實作 stack,
然後在裡面跑模擬的遞迴... 迴圈跟遞迴應該是有方法能夠機械轉換，
雖然不見得容易。最常見的方法，或許是把遞迴轉換成 tail recursion,
透過 continuation-passing style 或其他類似的技巧。而一旦可以轉成
tail recursion, 則很容易再轉成迴圈的方式。

不過如果要反過來轉就不太容易了，這就有點像是反組譯的味道了，
還是高階轉低階，遠比低階轉高階容易...

Edward 說他用了一個 lisp 的 macro + function 寫出來了。
我猜就是類似動態產生 for n in ns 那樣吧？這種作法應該是很直觀，
不過我不會 lisp 不知道要怎麼寫... (p.s. clisp build 失敗 ><)

用 haskell 呢？第一個想到的就是 list comprehension.
不過很不幸的是，看來我的敏感度還不太高，稍微想了一下，
已經快要湊出正確答案了，卻在前一刻放棄，google 到了正解。

很簡單的想法。假設現在的 list of lists 又再增加一個 list,
那麼答案會怎麼改變？大概就是把原本的每一個結果的 list 抽出來，
再把新 list 裡的每一個 element 跟每一個結果 cons 起來。

這很明確就是 concatMap 的動作。寫作過程大概是像這樣... 開頭一定是：

combos0 :: [[a]] -> [[a]]
combos0 [] = [[]]
combos0 (xs:xss) = ...

然後一定會用到的是 (combos0 xss), 和 concatMap, 大概就是這樣：

concatMap (...) (combos0 xss)

接著我們知道 concatMap 的第一個 argument, 也就是應該填一個
lambda 進去的那邊，會得到其中一個 result list, 這邊寫作 rs:

concatMap (\rs -> ...) (combos0 xss)

接下來要在 rs 上面接上新 list, 也就是 xs 裡面的元素，我們知道一定是：

x:rs

而這個 x 則是來自 xs 裡面。因此很容易可以看出這邊一定有：

map (...) xs

綜合上面的結論，x 要接上 rs, 則可以找到：

\rs -> map (:rs) xs

最後整個組起來，就會是：

combos0 (xs:xss) = concatMap (\rs -> map (:rs) xs) (combos0 xss)

我們就得到 concatMap 版的 combos 了...
寫成直觀一點的 list comprehension, 就會是
x : rs, 而 x 來自 xs, rs 來自 combos1 xss.

combos1 (xs:xss) = [ x : rs | x <- xs, rs <- combos1 xss ]

我想到這邊都還很好懂。但用上 list monad 就覺得很神奇了，
得承認多給我一點時間，大概也想不出這種作法 @@
不過要解釋的話倒不是很難，只要知道這些 function 背後的定義，
稍微展開改寫一下就可以推衍出來。

首先我們要先知道 list comprehension 可以看成一種 list monad,
也就是以下兩者是等價的：

[   (x, y) | x <- [1..2], y <- [3..4] ]
do{          x <- [1..2]; y <- [3..4];  return (x, y) }

因為 list monad 的 >>= 其實也就是 concatMap...
照同樣的規則的話，可以把上面的 list comprehension 改寫成：

do{ x <- xs; rs <- combos2 xss; return (x : rs) }

而這個形狀，又正好是 liftM2 的樣子。也就是把 cons 變成
monadic cons, 就可以改寫成：

combos3 :: [[a]] -> [[a]]
combos3 [] = [[]]
combos3 (xs:xss) = xs `monadic_cons` (combos3 xss) where
                       monadic_cons = liftM2 (:)

把上面的式子展開，則可以得到：

xs `monadic_cons` (xs' `monadic_cons` (xs'' `monadic_cons` ...))

這不正是 foldr 嗎？於是改寫成 foldr, 連 argument 都能省掉了：

combos :: [[a]] -> [[a]]
combos = foldr (liftM2 (:)) [[]]

唔... 解釋起來很簡單，但看到這種結果，還是不禁想問，
要如何進入 monad 的思考方式？還是說，其實每個人都是這樣慢慢
把程式推導出來，而不是一出手就這麼神妙？又或許其實練習，
真的能慢慢進入這種境界吧？到這種時候，又怎麼會想寫 c++?

combos.hs