再帰と言えばハノイの塔。ということでHaskell でハノイの塔をプログラムしてみた。
なお、前回の投稿にて、「いかにして問題をとくか」を参照した記事を書いたので、その時に復習した、問題解決手法を活用している。本記事の見出しは、その問題解決手法から引用している。
その問題を理解する
未知のものは何か（最終的に手に入れたいものは何か）
- ハノイの塔をHaskellで書いたときのコード
与えられたものは何か（手元にある道具は何か）
- 3本の杭
- 複数の円盤
条件は何か（未知のものと与えられたもととをつなげる条件は何か）
- 以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。
- 複数の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
- 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
- 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
問題を解くために計画を立てる
###条件を言い換えてみる
以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。〜最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
左側をスタート杭として、右側をゴール杭、真ん中を中継杭と呼べる。
円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
2回連続で、同じ杭に向けて円盤を移動することはできないので、まずは上の円盤を中継杭に移動してから下の円盤をゴール杭に移動するような操作となる。
問題を変えてみる（特殊化・帰納法）
複数の杭と、中央に穴の開いた大きさの異なる 複数の円盤 から構成される。
0枚の円盤から構成されていたらどうか
移動する円盤がないので、なにもしない。
１枚の円盤から構成されていたらどうか
スタート杭には円盤が1枚ある。この円盤を、ゴール杭に移動する。
２枚の円盤から構成されていたらどうか
スタート杭には円盤が2枚(上からx、y とする )ある。上の円盤xを中継杭に移動する。次に、下の円盤yをゴール杭に移動する。最後にx を中継杭からゴール杭に移動する。
３枚の円盤から構成されていたらどうか
スタート杭には円盤が3枚ある(上からx、y 、 z とする )。上の円盤 x を中継杭に移動・・というやり方ではなく再帰的に考えてみると、次のようになる 。
上の2枚の円盤(x 、y )を中継杭に移動する。次に、下の円盤 z をゴール杭に移動する。最後に、(x 、 y )を中継杭からゴール杭に移動する。2枚の円盤を移動するには、上述の 2枚の円盤から構成されていたらどうなるか を利用し、中継杭を仮のゴール杭と見立てて移動する。最後の操作も、中継杭を仮のスタート杭と見立てて移動する。
似たような問題を解いたことがないか
再帰のプログラムを自分で作ったことがある。 sum 関数とか。
その時はリストに対して、パターンマッチを使った再帰的な関数定義をした。ここではリストは使えそうにないから、それに相当する再帰処理が必要になると思われる。その場合は、計算の基底部とより小さな部分問題に切り分ける。
問いとなる円盤の枚数を開始値として、円盤が0枚になるまで再帰するような形となるだろう。
プログラムの方針
計算の基底部は、上述の 0枚の円盤から構成されていたらどうか から明らかになった。
また、３枚の円盤から構成されていたらどうか の考え方を一般化し、n枚の円盤をルール通りに移動するには、(n-1)枚の円盤をスタート杭から中継杭に移動させる 前処理 、残っている一枚をゴール杭に移動させたことを記録する 本処理 、(n-1)枚の円盤を中継杭からゴール杭に移動させる 後処理 に分解することで、より小さな部分問題とすることができた。
このプログラムをmove 関数として定義して、引数には 円盤の枚数 、 スタート杭はどれか 、 ゴール杭はどれか、 中継杭はどれか を情報にもつ Hanoi 型のデータを渡すことにする。
サンプルコード
-- | Hanoi は円盤枚数、スタートとゴール、中継地点をもつデータ構造
data Hanoi = Hanoi { number :: Int
, dep :: Position
, dest :: Position
, temp :: Position
}
-- 杭の位置付けを示す
data Position = A | B | C deriving(Show)
-- n 枚の円盤を、左端の杭から右端の杭に移動させ、結果をログとして記録する
move :: Hanoi -> [String]
move (Hanoi 0 _ _ _) = []
move (Hanoi n dep dest temp) =
move (Hanoi (n-1) dep temp dest) ++ [show dep ++ " -> " ++ show dest] ++ move (Hanoi (n-1) temp dest dep)
main = mapM_ putStrLn $ (move (Hanoi 3 A C B))
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
せっかくなので、Writer モナドを使ってみる
-- | Writer モナドを使って、結果なし、ログに移動手順を記録する
move :: Hanoi -> Writer [String] ()
move (Hanoi n dep dest temp) = do
case n of
0 -> return ()
n -> do
move (Hanoi (n-1) dep temp dest)
tell [show dep ++ " -> " ++ show dest]
move (Hanoi (n-1) temp dest dep)
-- | move関数のログを加工して出力する
runHanoi :: Int -> (Int, [String])
runHanoi n = let (_, log) = runWriter (move (Hanoi n A C B))
in (length log, log)
*Main> runHanoi 3
(7,["A -> C","A -> B","C -> B","A -> C","B -> A","B -> C","A -> C"])
振り返り
結果としてはHanoi 型の存在意義は、あまりないかもしれない。当初は、リストに変わる再帰的なデータ構造( Tree のような )をHanoiで実装したいと思っていたものの、停止性や部分問題を検討するうちにその必要がないことに気がついてしまった。
後日談： 手順ではなく、状態遷移の記録をとりたい
Qiitaの記事を大いに参考にさせていただき、手順ではなく杭と円盤の状態遷移を記録するための考え方を学んだ。
ハノイの塔をを別の観点から考える
ハノイの塔を別の観点から見てみると、n枚の円盤の移動はもともとスタート杭にnの円盤があった状態で、(n-1)枚の円盤をゴール杭に移動する 操作と、もともとゴール杭にnの円盤があった状態で、(n-1)枚の円盤をゴール杭に移動する 操作を活用することで問題を分解することができる。
操作を活用するとは、通常の(n-1)枚の円盤の移動に伴う状態遷移を、スタート杭とゴール杭、中継杭の関係性を変えることを指し、具体的には次の２点となる。
- スタート杭にnの円盤を置き、さらにゴール杭ではなく中継杭にn枚の円盤を移動したかのように変換する
- ゴール杭にnの円盤を置き、さらにスタート杭ではなく中継杭からゴール杭にn-1枚の円盤を移動したかのように変換する
ということで、仮にdoHanoi が３本の杭と円盤の状態遷移をリストで返す関数だとすると、とりあえず擬似的に次のように宣言できる。
doHanoi :: Int -> [([Int], [Int], [Int])]
doHanoi 0 = [([],[],[])]
doHanoi n =
map ('スタート杭にnの円盤を置き、ゴール杭ではなく中継杭にn枚の円盤を移動したかのように変換する') (doHanoi (n-1))
++
map ('ゴール杭にnの円盤を置き、スタート杭ではなく中継杭からゴール杭にn-1枚の円盤を移動したかのように変換する') (doHanoi (n-1)
サンプルコード
doHanoi :: Int -> [([Int], [Int], [Int])]
doHanoi 0 = [([], [], [])]
doHanoi n = map (\(xs, ys, zs) -> (xs ++ [n], zs, ys)) (doHanoi (n-1))
++ map (\(xs, ys, zs) -> (ys, xs, zs ++ [n])) (doHanoi (n-1))
doHanoi :: Int -> [([Int], [Int], [Int])]
doHanoi 0 = [([], [], [])]
doHanoi n = map (\(xs, ys, zs) -> (xs ++ [n], zs, ys)) (doHanoi (n-1))
++ map (\(xs, ys, zs) -> (ys, xs, zs ++ [n])) (doHanoi (n-1))
*Main> mapM_ print $ doHanoi 3
([1,2,3],[],[])
([2,3],[],[1])
([3],[2],[1])
([3],[1,2],[])
([],[1,2],[3])
([1],[2],[3])
([1],[],[2,3])
([],[],[1,2,3])