powerset (3) hanoi

看到老林在上篇 comment 裡提到的 hanoi,
我記得我那時候，有照著老林說的概念自己試過一次。
已經不記得那時候是試什麼，但概念倒是還記得，
走在路上時，就開始在想，是不是能重做一次看看？

結果還真的一試就成了...

只能說這個解釋確實很清楚好懂？大概是這樣的：
hanoi 的三個柱子，可以看成 source, buffer, 和 destination.
想像現在只有一個盤子要搬，那當然是 source => destination.
但如果現在要搬的盤子，上面還有其他盤子(n-1)，那必須把上面的先搬到
buffer, 然後把自己搬到 dest, 最後再把 buffer 裡的搬到 dest.

全部也只有這個動作而已。因為我們可以互換每個柱子的角色。
當我們要把上面的盤子(n-1)搬到 buffer, 我們可以互換 buffer
與 dest 的角色，也就是說把 buffer 當 dest, 把 dest 當 buffer.

而因為你要搬 n 時，要先搬 n-1, 要搬 n-2 時，要先搬 n-1,
所以實際上只要不斷變換柱子的角色，就能把整個過程看成一種遞迴，
實際上真正的操作，只有 source => destination,
其餘都是讓 buffer 與 dest 互換，還有讓 buffer 與 source 互換。
後者是從 buffer 搬到 dest, 讓 source 變成 buffer 的意思。

寫成表大概像這樣：

(n-1) source => buffer (buffer 與 dest 互換)
(n) source => destination (唯一真正的移動)
(n-1) buffer => destination (buffer 與 source 互換)

翻譯成 Haskell, 一開始我是寫成這樣：
n 是盤子編號，f 是 from(source), b 是 buffer, t 是 to(dest),
而 r 則是 result, 所有步驟的 List.

ha :: Integer -> Char -> Char -> Char -> [(Integer, Char, Char)] -> [(Integer, Char, Char)]
ha 0 _ _ _ r = r
ha n f b t r = ha (n-1) f t b r ++ [(n, f, t)] ++ ha (n-1) b f t r

試了一下，看起來真的是對的。很少一寫就成過...
雖然我原本是想把柱子寫成 List, 像是：

hanoi :: List a -> List a -> List a -> ...

但想來想去，這樣做的話就不知道怎麼互換柱子了？
只好還是用代號表示柱子。或許要把這當成某種 flag, 才能做 List.

然後覺得 r 很多餘，可以改成：

ha' :: Integer -> Char -> Char -> Char -> [(Integer, Char, Char)]
ha' 0 _ _ _ = []
ha' n f b t = ha' (n-1) f t b ++ [(n, f, t)] ++ ha' (n-1) b f t

接著可以省掉一個 ++, 雖然我不知道有沒有意義...

ha'' :: Integer -> Char -> Char -> Char -> [(Integer, Char, Char)]
ha'' 0 _ _ _ = []
ha'' n f b t = ha'' (n-1) f t b ++ ((n, f, t) : ha'' (n-1) b f t)

我想這樣再來看這個（Zelda triangle（誤）），應該比較容易懂吧？
ICFP 2009 演講全程錄影上網