ハノイの塔

Haskell のIOモナドと格闘しているうちに、Haskell が普通のプログラミング言語だということが感じられてきた。恐れられているIOモナドだって、「引数が一つで戻り値がIO型」の関数(アクション)を >>= 演算子でつないだだけというイメージができれば、不可思議だったエラーメッセージがでてもなんとか対応できるようになった。圏や関手や副作用や実行順序などの面倒な考察は一切不要だ。

Haskell でプログラムを作るのに慣れてきたので、Haskell に何かをやらせたくなった。楽しみで Haskell を使うのなら、やはり、パズルだろう。そういう訳で、有名な「ハノイの塔」のパズルを解かせるプログラムを書いてみた。

ハノイの塔というパズルは、細長い台に3本の支柱が立っていて、それに中心に穴の開いたドーナッツ状の円盤が重ねられて刺さっている。円盤は上に行くほど小さくなるので、全体としてピラミッド型をしている。円盤は最初全てが左端の支柱に刺さっているが、それを右端の支柱に移すのがパズルの目的だ。ただし、円盤は一度に一枚しか移動できない。また、小さい円盤の上にそれより大きな円盤を重ねることはできない。このパズルを解くプログラムを作ってみようという訳だ。

パズルを解くといっても、自分で考えつくわけはないので、Google 先生で探し回ったところ、次のように考えればよいということが分かった。

まず3本の支柱をアルファベットの A B C で識別することにする。円盤は最初全て A の支柱に重ねられていて、それを、C の支柱に移動することになる。ここで、Aの円盤全てがCの円盤全てに移されるときの最終段階の様子を考えてみる。仮に円盤の個数が n 個であったとする。また、円盤には上から順番に 1..n の番号が割り振られているとする。

すると、一番大きな n の円盤をAからCへ移すためには、n-1個の円盤が B の支柱に重ねられている必要がある。なんらかの方法でその操作を終えたのち、AからCへ n の円盤を移すことができる。そのうえで、また、何らかの方法で B に重ねてある n-1 個の円盤を、Cに刺さっている n の円盤の上に重ねてやれば移動は完了する。

そこで、n 個の円盤を何らかの方法で移動させることを、hanoi n from work to という関数で表すことにする。hanoi が関数名、 n が円盤の数、from は移動前に円盤が重ねられていた支柱の名前、work は作業用に利用された支柱の名前、to は最終的に n 個の円盤が移動した支柱の名前だ。

そうすると、n 個の円盤全部を支柱 A から支柱 C へ移動させる方法は、hanoi n 'A' 'B' 'C' で表せる。n-1 個の円盤を支柱 A から支柱 B まで移動させる方法は、hanoi (n-1) 'A' 'C' 'B' だ。また、n-1 個の円盤を支柱 B から支柱 C まで移動させる方法は hanoi (n-1) 'B' 'A' 'C' だ。さらに、支柱Aから支柱Bへn番の円盤を移動することを、(n, 'A', 'B') の三つ組で表すことにする。

これらの抽象的な考察をもとに作ったのが次のプログラムだ。hanoi がどういう関数なのかという内部構造には一切触れず上の考察をそのままプログラムにしている。

hanoi 0 _ _ _ = []
hanoi n from work to =
  hanoi (n-1) from to work ++
  [(n, from, to)] ++
  hanoi (n-1) work from to

一行目の定義は hanoi 関数の終了条件で、これがないとスタックがオーバーフローするまでプログラムが止まらない。この意味は、円盤の数が0の時はなにもしないという意味だ。

実行例は次のようになる。

Main> hanoi 2 'A' 'B' 'C'
[(1,'A','B'),(2,'A','C'),(1,'B','C')]
Main> hanoi 3 'A' 'B' 'C'
[(1,'A','C'),(2,'A','B'),(1,'C','B'),(3,'A','C'),(1,'B','A'),(2,'B','C'),(1,'A','C')]

ちゃんとパズルの回答が出力されているのに不思議な気がする。繰り返しのある構造のデータについて、ある一点でのデータ構造を記述することで全体の動きをプログラムできる再帰的定義の威力を感じさせる例だ。

Haskell を使うとだんだん馬鹿になるそうだ。スタックやキューやデータ構造などを考えなくても、アルゴリズムをPerl で文字列を扱うときのように記述できてしまう。Haskell のプログラム例の解読の難しさは、言語操作の難しさではなく、アルゴリズムそのものの難しさなのだろう。


今日のHaskell
Main> lcm 12 15
60
Main> gcd 12 15
3

最小公倍数と最大公約数
[PR]
by tnomura9 | 2010-11-20 16:05 | Haskell | Comments(0)
<< Ruby 版ハノイの塔 二分木探索 >>