Haskell と数学パズル

Haskell のおもしろい使い方をネットで検索するにはどうすればよいかと考えて、「Haskell パズル」で Google 先生に聞いてみた。いろいろなパズルを Haskell で解いてあったが、「窓際プログラマーの独り言 -C#の話題を中心に」というブログの記事の問題が面白かった。

3桁の整数とその2乗の数の数字が、1から9までの数字が一回だけ現れるような3桁の整数はなにかという問題だった。たとえば、763*763=582169だが、4が抜けているし6が2回現れている。

詳しい解き方は、元記事を読んでもらえば分かるが、投稿されていた解法に次のようなものがあった。

import List
main = print [n | n <- [100..999],(sort( show (n * (1000000 + n))))=="123456789"]

この解法の工夫されているところは、n*(1000000 + n) で元の数値と、その数の2乗の値を同時に表示しているところ。数値を show 関数で数字の文字列に変換し、さらにそれをソートすることで、1から9までの数値が1回ずつ現れるという問題を、"123456789"という文字列との比較という形に持ち込めたことだろう。また、3桁の数値を一つずつ検証して目的の数値を取り出すのに、リストの内包的表記が使われている。

リストの内包的表記は、集合の内包的定義とほぼ同じだ。数値 n の集合を求める定義だけれど、その数値は、n <- [100..999] だから100から999までの3桁の整数の集合の要素だ。その要素のうち、sort(.....)=="1..9" の条件に適合するものだけを抜き出してリストにしてくれる。

使い勝手のいい表記で、一つのリストから条件に合うものを拾い出すだけなら filter でもできるが、二つ以上のリストから新しいリストを作ることもできる。例えば、1から6までの数の対を全て作りたいときは、[(x,y)| x <- [1..6], y <- [1..6]] で簡単に全ての組み合わせを作ることができる。表記の意味はほとんど集合の内包的定義と同じなので、集合を定義する感覚で気楽に記述できる。プログラムの記述から考えると変則的な感じもあるが、集合の定義をそのままプログラムとして記述できるのは、問題のモデル化には非常に便利な道具となる。

アルゴリズム的には単に全ての3桁の数をチェックしているだけの力業なのだけれど。問題のパズルの内容をHaskell の言葉でどう表現するかというところがおもしろい。プログラムするのにループもインデックスも使わないでいいというのはかなり快適な体験だ。

Haskell でプログラムを作るときに2つの要因がある。一つは、ハノイの塔の場合のように、純粋なアルゴリズムとしての問題。もう一つは、自然言語として表現された問題をどう Haskell の言葉としてモデル化することができるかという問題だ。

このプログラム言語による現実の問題のモデル化という作業が、Haskell では手続き型のプログラムよりも楽なような気がする。リスト操作のための map, filter, foldr などの高階関数は一度手にすると手放せなくなる。また、ループを再帰関数で表現するのも最初は抵抗があるが、慣れてくればインデックスや比較演算なしにパターンで表記できる快適さを感じるようになるだろう。

思考の補助手段としてのプログラム言語としては、Haskell はかなりストレスを感じさせない言語だ。汎用のプログラム言語であるにもかかわらず、現実の状況をモデル化する簡潔な表現が揃っている事がその理由のひとつだろう。


今日の Haskell
1から9までの数列をスペースを挿んで表示するには?
Hugs> putStrLn (unwords $ map show [1..9])
1 2 3 4 5 6 7 8 9
[PR]
by tnomura9 | 2010-11-21 21:50 | Haskell | Comments(0)
<< 3の倍数と3のつく数 Ruby 版ハノイの塔 >>