読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskell入門 リスト内包表記を利用して鶴亀算を解く

1.頭の体操

ウィキペディアによると、鶴亀算は中国の数学書「孫子算経」の中にある「雉兎同籠」(雉:キジ、兎:ウサギ)が始まりとされている。これが江戸時代になって、目出度い動物である鶴と亀に変わったそうである。小学校の時代に解いた経験を持つ人も多いことと思われる。中学校に入ると方程式を利用できるようになるので、簡単に解けるようになるのだが、頭の体操としてよく用いられる。

学びの場を見ると、次のような問題が出ている。

1)準備体操:鶴と亀が合わせて6 匹いる。足の合計が2 0 本であった。 鶴と亀はそれぞれ何匹いるか? (鳥は1 羽2 羽と数えるが、ここでは「匹」としておく)

2)難易度1:鶴と亀が合計8 0 匹いる。足の数の和が2 0 0 本であったとき、鶴と亀はそれぞれ何匹いるか?

3)難易度2:5 0 円切手と8 0 円切手を合計1 4 枚買って1000 円を支払った。 5 0 円切手と8 0 円切手をそれぞれ何枚買ったか。

4)難易度3:次 のルールでカードゲームを2 人で行った。 (ルール)じゃんけんで勝てば、相手から2 枚のカードをもらう。 負ければ1 枚渡す。 私は最初10 枚のカードを持っており、7 回じゃんけんを行ったら私 のカードが15 枚になった。私は何回勝ち、何回負けたか。ただし、引き分けはなかった。

小学生になったつもりで鶴亀算で、中学生になったつもりで方程式を利用して上の問題を解いてみると、小中学校時代のことを思い出せて楽しいことと思う。

2.リスト

Haskellは数学の圏論をベースにしたプログラミング言語である。圏論は、集合、グラフ、トポロジーなどを統一的に扱う数学である。圏論の教科書を開くと多くのものは集合から始まっていると思う。Haskellも集合に対しては、リストと呼ばれる便利な方法を提供している。

例えば、1から10までの整数の集まりは、

[1..10]

と記述する。

また、2から10までの偶数の集まりは、最初の要素と二つ目の要素をカンマで区切り、

[2,4..10]

と記述する。

また、奇数の集合を求めたければ、最初の要素と二つ目の要素だけを与えて、

[1,3..]

とすればよい。これは無限に続く数なので表示できないが、最初の10個を取り出したいときは、

take 10 [1,3..]

とすればよい。これは遅延評価と呼ばれる。遅延評価は必要になるまで計算を行わず本当に必要になった時に計算を行うもので、Haskellが有する有力な武器の一つである。上記の場合は、[1,3..]の計算がtake 10により要求されたので、最初の10個だけを取り出している。一般に、多くのプログラミング言語は奇数のように無限に続くものを扱うことができないが、無限な要素を持つ集合を使えるようにしたのは、Haskellの優れた点である。

リストは順番がついているものであれば、なんでも利用することができる。例えば、アルファベットの小文字は以下のようになる。

['a'..'z']

3.リスト内包表記

準備体操1の問題は、「鶴と亀が合わせて6 匹いる。足の合計が2 0 本であった。 鶴と亀はそれぞれ何匹いるか?」となっている。この問題では鶴の可能な数の集合は0から6までとなるので、Haskellでは次のように表すことができる。

[0..6]

そこで、それぞれの足の数の集合は、それぞれの数に2をかけたものなので、

[2 * x | x <- [0..6]]

となる。これは、次のように読める。この集合は、2*xの集まりで、xは[1..6]の要素である。これはリストの内包表記と呼ばれ、縦棒の右側は集合を、左側はその条件を表す(この概念は集合の内包的記法に近い)。

それでは、鶴と亀が合わせて6匹いるとき、鶴と亀の可能な組み合わせはどのようになるかを記述すると次のようになる。

[(x, 6 - x) | x <- [0..6]]

上記を実行したとき、[(0,6),(1,5),(2,4),(3,3),(4,2),(5,1),(6,0)]をえる。カッコ内の左側が鶴の数、右側が亀の数である(なお、カッコはタプルと呼ばれる)。それでは、その時の足の数を求めてみる。これは次のようになる。

[(2 * x, 4 * (6 - x)) | x <- [0..6]]

これを実行すると次のものを得る。
[(0,24),(2,20),(4,16),(6,12),(8,8),(10,4),(12,0)]
この中で、足したとき20になっているのが解であるが、解の集合を得るためには、条件のほうに足の総数が20であることを示せばよいので次のようになる。

 [(x, 6 - x) | x <- [0..6], 2 * x + 4 * (6 - x) == 20]