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

bitterharvest’s diary

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

HaskellドリルⅡ 再帰的なデータ型を作成する

1.名称が猛々しい代数的データ型

代数的データ型の話は、以前の記事で少しふれた。今回は、もう少し詳しく説明する。「すごいHaskell楽しく学ぼう!」でのリストと木構造を用いての論理的な説明が分かりやすいので、ここでも、リストと木構造を用いて説明する。

最初に代数的データ型を定義しておく。代数的データ型は、一個以上の値コンストラクタがあり、それぞれの値コンストラクタは引数を持つ場合もあるし持たない場合もある。この定義からわかることは、代数的データ型は値コンストラクタを持つことが要請される。前の記事で述べたキーワードdataを用いて新しいデータ型を定義したが、それらは、皆、代数的データ型である。代数的データ型という名前は何となく仰々しいように思えるが、なぜ、そのような名前になっているかは、以前の記事を読んでもらうと分かる。

2.再帰的な定義を可能にする代数的データ型

再帰的な表現は、人形の中に人形が入っているマトリョーシカ人形のような、有限あるいは無限な入れ子状態を説明するのに優れている。

植物の枝を説明するときに、大きな枝は小さな枝の集まりで構成され、小さな枝は細い枝で構成されている。この表現は、枝という言葉を再帰的に用いて、木の茂みを説明している。

会社の組織についても同じようなことがいえる。会社は一つの大きな組織である。その組織はいくつもの小さな組織で構成されている。さらに、小さな組織もさらに細かい組織で構成されている。この表現では、組織ということが再帰的に使われている。会社では、便宜的に組織の大きさを表すために、事業所、部、課、係などの用語が使われている。

そこで、まず、リストを考えてみることにする。文字列”word”は文字'w','o','r','d'を並べたもの、即ち、リストである。これは、Haskellの内部では、'w':'o':'r':'d':[ ]と表現される。リストの一番右側には空のリスト[ ]が存在する。これは、文字列に限らずすべてのリストに共通である。リストを構成するものは、①空のリストEmpty、②すでにあるリストに新たな要素を左からくわえるConsであると考えると、リストが定義できる。これは次のようになる。

data List a = Empty | Cons a (List a) deriving (Show, Read, Ord, Eq)

上記のプログラムで、等号の左側のaは型変数である。これは、Consを行うときは、加える要素の型と、すでにあるリストを構成している要素の型が同じであると制約している。Consの右側で、要素のaとリストのaが一緒だが、これは型が同一であるといっているだけで、値が一緒であるとは言っていない。

Consの型シグネチャは次のようになっている。

Prelude> :t Cons
Cons :: a -> List a -> List a

入力にも出力にもListが現れるので、再帰的であることが確認できる。

木構造は多数の枝を持つことが可能であるが、ここでは、二つの枝(二分木)を有するものと限定する。リストと同じように、全くない状態をEmptyTreeとし、二分木を作成するものをNodeとすると、Listからの類推により次のように定義できる。

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Ord, Eq)

木を作成している例を以下に示す。

Prelude> data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Ord, Eq)
Prelude> let b1 = Node 3 EmptyTree EmptyTree
Prelude> let b2 = Node 5 EmptyTree EmptyTree
Prelude> let b3 = Node 15 b1 b2
Prelude> let b4 = Node 20 b3 EmptyTree
Prelude> b4
Node 20 (Node 15 (Node 3 EmptyTree EmptyTree) (Node 5 EmptyTree EmptyTree)) EmptyTree

Nodeの型シグネチャを見ると次のようになっている。

Prelude> :t Node
Node :: a -> Tree a -> Tree a -> Tree a

やはり、入力にも出力にもTreeが現れるので、再帰的であることが確認できる。

3.問題

それでは問題に移る。

問題1.リストの要素数を求める関数を定義しなさい。

問題2.与えられた木構造のNodeの数を求める関数を定義しなさい。

問題3.与えられたリストを2等分し、さらに2等分されたリストをそれぞれ2等分するという操作を繰り返すことで、木構造が得られる。但し、2等分しようとするものの数が奇数である時は、右側を一つ大きくすることで2等分する。上記の操作を利用して、リストを木構造に変換する関数を定義しなさい。

問題4:枝分かれする数が二つではなく、一つ以上である場合、どのような代数的データ型を用意したらよいか説明しなさい。

問題5:上記で定義した代数的データ型を用いて、企業の組織がどのように表されるか説明しなさい。

問題6:与えられてリストを3等分し、さらに3等分されたリストを3等分するという操作を繰り返すことで、3分枝の木構造になる。なお、3等分できないときは、余ったものを右のほうから埋めていくことにする。上記の操作を利用して、リストを木構造に変換する関数を定義しなさい。

問題7:与えられた木構造の要素(ノード)は、大小が比較できる型であるとする。この時、その木構造の中で最大のものを見つける関数を定義しなさい。

問題8:上記において最小のものを見つける関数を定義しなさい。

問題9:与えられた木構造の要素(ノード)は加算が可能な型である。そこで、すべての要素の和を求める関数を定義しなさい。

問題10:スポーツや勝負事の世界で用いられるトーナメントは二分木の例である。そこで、(直下がEmptyTreeになっている)末端のノードには選手の名前が、そうでないノードには、その直下のノードの選手同士が戦った時の勝者の名前が入るようにしたい。あるトーナメント試合の結果を木構造で表しなさい。