ハノイの塔

http://d.hatena.ne.jp/yone-chan/20071231
再帰の美しいアルゴリズムです。
Haskellに移植してみました。hanoi関数からIOを分離しています。

module Main (main) where

hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi _ _ _ 0 = []
hanoi a b c n =
    hanoi a c b (n - 1) ++ [(a, b)] ++ hanoi c b a (n - 1)

main :: IO ()
main = putStr $ concatMap (\ (a, b) -> a ++ " -> " ++ b ++ "\n") $ 
         hanoi "a" "b" "c" 3
-- => a -> b
--    a -> c
--    b -> c
--    a -> b
--    c -> a
--    c -> b
--    a -> b

参照: ハノイの塔 - Wikipedia