powerset (4)

不知為何，我似乎很喜歡這個題目。可能是因為以前寫不出遞迴式，
而今天卻覺得這如此直覺，因此有覺得看到這就想到某種啟發的感覺
吧..? 而原本寫不出來的原因，我猜大概是因為遞迴本身有兩個點。
就算寫了 sub = powerset ... 然後在兩個地方使用 sub, 但這應視為
實作細節，實際上還是 refer 到兩次。

我在想，或許本來就應該背一些定石吧。（推卸無法原創的責任..）

總而言之，我是從那神奇的：

powerset = filterM (const [True, False])

倒推回來，才漸漸真的理解 powerset 的遞迴式，進而有辦法真的
憑空寫出來，而不是去翻之前到底是怎麼寫的..。

遙記以前第一次寫 powerset 時，還很笨地用一個大整數去跑的。
而這需要實作 BigInt, 或是使用 dynamic bitset... 沒記錯的話，
這還是老林提示我的？當時還在玩 c++..

*

這一兩天，大概是因為跟人討論到 recursion 的東西（啊不知道
要不要把那篇貼上來），因此又開始想起這些 powerset 的事情。

於是重新回想，試著再多實作幾種方法試試。

第一種方法，就是上面那個神奇的 filterM. 當時看懂之後，就寫了
一個把 monad 拆開的版本。這在頭一篇裡就有提到這件事了。

第三個版本，則是我這兩天重新思考過 filterM 後的結果。簡單地說，
就是最普通的遞迴式，沒有 monad, 沒有 [True, False] 這種奇怪的
東西。

powerset'' :: [a] -> [[a]]
powerset'' [] = [[]]
powerset'' (x:xs) = map (x:) (powerset'' xs) ++ (powerset'' xs)

然後心裡就開始覺得，這應該才是最正確的版本，可以非常清楚看出
這是什麼意思，事實上也是實際演算法真正在做的事情。想到這裡，
不禁開始想，就效率而言，這應該也是最好的吧？同時又另外寫了一個
如果要用 monad, 但是不用 filterM 的版本。看起來其實也很單純：

powerset''' :: [a] -> [[a]]
powerset''' [] = [[]]
powerset''' (x:xs) = do
  flag <- [True, False]
  ys <- powerset''' xs
  if flag then
    return (x:ys)
  else
    return ys

接著最後又在想，既然我都跟別人提到 tail recursion 了，何不
也寫個 tail recursion 的版本？然後還可以測測效能呢。不過之前
練習 tail recursion 的時候，搞到自己沒什麼自信...。昨晚因為電腦
已關，因此用紙筆盤算了一下。亂寫一通，然後用筆展開看看對不對。

事實證明，還是用電腦比較好 XDD 我展開都展錯了。太懶了，很多
重複的東西都懶得一直寫，然後就一直看錯又寫錯... 自己字又難看，
又常常寫得亂七八糟，現在仔細想想，搞不好這是自己數學很爛的
原因之一 XDDDD 因此借助電腦之後，反而發現自己搞懂很多東西？

總而言之，基本上幾乎完全是照直覺去寫，然後把 type 弄對，今早在
電腦上試了一下，還真的就寫對了。基本想法大概類似，把所有需要
遞迴的點，往 continuation 的那個 function 裡丟就對了。然後那個
continuation 只有一個參數，就是原本的遞迴結果。

因此 map (x:) (powerset'' xs) ++ (powerset'' xs) 就變成
\r -> map (x:) r ++ r

老實講我有點不記得當初學的時候是不是這樣學的。我感到很意外的是，
真的有很多很多的東西，在當初聽的時候懵懵懂懂，可是後來卻又覺得
那好像是異常直覺的事情。就像是想睡覺時想破頭也想不出來，隔天清晨
醒來卻忽然覺得一切都是如此自然，搞不清楚為什麼昨天自己會卡在那。

這大概也意味著，懂的人跟不懂的人之間，真的會有可怕的鴻溝吧.. (苦笑)
畢竟連自己身上都能出現這種事了。

tail recursion 的版本大概長這樣：

powerset'''' :: [a] -> [[a]]
powerset'''' = (powerset''''rec (:[])) . reverse

powerset''''rec :: ([a] -> [[a]]) -> [a] -> [[a]]
powerset''''rec k [] = k []
powerset''''rec k (x:xs) = powerset''''rec (\r -> (map (x:) (k r)) ++ k r) xs

我想了一下還是想不到為什麼要把 input reverse 一次才會得到跟原本
一樣的結果。這個大概是這兩天走在路上的題目吧，現在沒空想原因..

接著就是有趣的 benchmark 了。預測的結果大概會是：

tail recursion > recursion = monad = concat map = filterM

跟得到的結果差距不小......

filterM > tail recursion > monad > recursion = concat map

而且 filterM 還比 tail recursion 快很多，而 tail recursion 也只比
monad 快一點，更神奇的是，最普通的 recursion 居然是最慢的 @@
該不會是 ghc 7 有針對 filterM 和 monad 有做些神秘的最佳化？

不過雖然完全不符合我的預期，卻還滿高興得到這個結果的。因為：

1. 改寫 tail recursion 是有意義的
2. 用最抽象的 filterM 去寫是有意義的...
3. 用 monad 去寫是有意義的

而最直覺的 recursion 跑最慢，啊啊，懶人得不到好結果 (?

其實我在紙筆上展開 tail recursion 時，還覺得搞不好這樣不會比較快，
因為雖然可以靠 TCO 把 recursion 拔掉，但同時也產生了一個很巨大
很複雜的 closure 結構，因此讓我展開時一直寫錯。這樣原本可能導致
stack overflow 的程式，改成這樣可能反而吃掉一堆記憶體，也讓 GC
變得超級忙碌..? 或是說，要在進入這個 function 前，暫時關閉 GC??

所有程式可以在 powerset.hs 找到。