What have you found for these years?

2009-11-30

powerset

其實我從來沒有真的自己寫過遞迴的 powerset ><
以前寫出來的都是暴力法,例如用 bitset 去 mask...
別人寫的遞迴自己也都看得似懂非懂。

我覺得,其實 recursion 和 monad 有點類似,
都是基本概念很簡單,一步一步拆出來很容易懂,
但就是有種見樹不見林的感覺 :( 覺得地圖還沒畫出來...
我還沒辦法用 recursion 和或 monad 思考,沒有進入那種模式。
目前思考還是很 imperative...

看了 jinjing 的 Haskness code,
覺得一切都是如此神奇...

powerset = filterM (const [True, False])

這實在是簡潔到恐怖的地步了。filterM 很神奇嗎?也沒有...
看起來就是很好想像的 filterM, 就是 filter 作用在 monad 上嘛。

稍微把 filterM 用 bind (>>=) 改寫,因為我還沒辦法用 do 思考...
不過發現自己已經能很輕易地把 do 改寫成 bind, 都很直覺了。
寫出來後就立刻意識到為什麼是從 ys 開始 iterate, 而非 flg.
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ [] = return []
filterM p (x:xs) = do
flg <- p x
ys <- filterM p xs
return (if flg then x:ys else ys)

看這個我直覺會從 flg 開始 iterate, 因此應該是 True, False, True, ...
但改成 bind 就很明顯:
p x >>= (\flg -> (filterM p xs >>= (\ys -> return ...)))
從 ys 開始做,所以當然從 ys 開始 iterate,
因此是 True, True, True, True, False, False, False, False...
do 的順序是反過來的,好像從來沒記住這一點。

這樣就能明顯看出,True 表示把頭接到身體上,False 就是不接。
像是 1 和 [2,3] 取 combo 就是 [1,2],[1,3]...
怪怪的,該怎麼講好 ><
假設我們已經有 [2,3] 的 powerset, 這樣要怎麼推出 [1,2,3] 的 powerset?
很明顯就是兩個 case (True, False), 一個是在每一個 set 上都加上 1 (True),
另一個就是什麼都不要動 (False), 因此 size 是 *2

把這個翻譯成一般的程式,就是:
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = concat $ map (powerset') [True, False] where
-- powerset' :: Bool -> [[a]]
powerset' flg = map (\ys -> if flg then x:ys else ys) (powerset xs)

(我不懂為什麼 powerset' 的 type 寫出來會不能過!?有錯嗎??)
(明明寫到外面去就可以用啊...? rigid type variable 是啥..)
(晚了所以下次再 google...)
這樣寫一次,感覺好像就豁然開朗了??
雖然其實我只是在做翻譯而已... :/

感覺這些東西都是說穿了很簡單。但,一開始是怎麼想到可以這樣寫的?
怎麼那麼漂亮就能用這種形式表達..?
這樣似乎就會有某種錯覺,覺得好像這個世界,都是用同一種 pattern 組成...
各個 model 之間都能夠互相轉換似的。

這樣有 category 的味道嗎? XDDD

==
真的覺得最神奇的部份,就是你會發現其實很多看起來毫無關聯的東西,
最後都是有關聯的。雖然說每個人都在這樣說,例如 PhD 這個名稱。
但是不管說得再天花亂墜,自己體會一次還是會有那種讚嘆感...
感覺這種事實在很難用「說服」的。

5 retries:

老林 said...

這不是和我用 OCaml 終於寫出 the tower of hanoi 時的感觸一樣嗎 XD

以前從沒真的搞懂過。

貼一個 OCaml 版本的類似東西 XD

(* Return a list of all sublists of l *)
let rec sublists l = match l with
[] -> [[]]
| x::xs ->
(sublists xs) @
(List.map (fun l -> x::l) (sublists xs))

那個 at 符號就是把 head @ tail 串起來的意思,
List.map 應該在所有 functional language 裡概念是一樣的吧。
在上述程式中會把 x 與 (sublists xs) map 起來,
這一段當初是從別人的 sample code 那看到的,
看懂之後印象超級深刻 ...

老林 said...

wacow, indent 全毀了,不過應該還是看得懂吧。

老林 said...

而且這字體的小寫 l 和 pipe "|" 根本分不出來嘛 wwww

godfat 真常 said...

測試 pre tag:
失敗... 來查查 blogger 能怎麼開放 pre tag @@

pre tag 有用的話就會用 bitstream or monaco or courier new

演算法其實根本就一模一樣嘛 @@
有接上 x 的就是 True, 沒有的就是 False.

godfat 真常 said...

好像無法耶... 要 hack 嗎?
還是乾脆換最流行的 wordpress 算了...

Post a Comment

All texts are licensed under CC Attribution 3.0