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 這個名稱。
但是不管說得再天花亂墜，自己體會一次還是會有那種讚嘆感...
感覺這種事實在很難用「說服」的。