What have you found for these years?

2010-07-20

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

0 retries:

Post a Comment

All texts are licensed under CC Attribution 3.0