１．名称が猛々しい代数的データ型
代数的データ型の話は、以前の記事で少しふれた。今回は、もう少し詳しく説明する。「すごいHaskell楽しく学ぼう!」でのリストと木構造を用いての論理的な説明が分かりやすいので、ここでも、リストと木構造を用いて説明する。
最初に代数的データ型を定義しておく。代数的データ型は、一個以上の値コンストラクタがあり、それぞれの値コンストラクタは引数を持つ場合もあるし持たない場合もある。この定義からわかることは、代数的データ型は値コンストラクタを持つことが要請される。前の記事で述べたキーワードdataを用いて新しいデータ型を定義したが、それらは、皆、代数的データ型である。代数的データ型という名前は何となく仰々しいように思えるが、なぜ、そのような名前になっているかは、以前の記事を読んでもらうと分かる。
２．再帰的な定義を可能にする代数的データ型
再帰的な表現は、人形の中に人形が入っているマトリョーシカ人形のような、有限あるいは無限な入れ子状態を説明するのに優れている。
植物の枝を説明するときに、大きな枝は小さな枝の集まりで構成され、小さな枝は細い枝で構成されている。この表現は、枝という言葉を再帰的に用いて、木の茂みを説明している。
会社の組織についても同じようなことがいえる。会社は一つの大きな組織である。その組織はいくつもの小さな組織で構成されている。さらに、小さな組織もさらに細かい組織で構成されている。この表現では、組織ということが再帰的に使われている。会社では、便宜的に組織の大きさを表すために、事業所、部、課、係などの用語が使われている。
そこで、まず、リストを考えてみることにする。文字列”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が現れるので、再帰的であることが確認できる。
３．問題
それでは問題に移る。
問題１．リストの要素数を求める関数を定義しなさい。
問題２．与えられた木構造のNodeの数を求める関数を定義しなさい。
問題３．与えられたリストを2等分し、さらに2等分されたリストをそれぞれ2等分するという操作を繰り返すことで、木構造が得られる。但し、2等分しようとするものの数が奇数である時は、右側を一つ大きくすることで2等分する。上記の操作を利用して、リストを木構造に変換する関数を定義しなさい。
問題４：枝分かれする数が二つではなく、一つ以上である場合、どのような代数的データ型を用意したらよいか説明しなさい。
問題５：上記で定義した代数的データ型を用いて、企業の組織がどのように表されるか説明しなさい。
問題６：与えられてリストを3等分し、さらに3等分されたリストを3等分するという操作を繰り返すことで、3分枝の木構造になる。なお、3等分できないときは、余ったものを右のほうから埋めていくことにする。上記の操作を利用して、リストを木構造に変換する関数を定義しなさい。
問題７：与えられた木構造の要素(ノード)は、大小が比較できる型であるとする。この時、その木構造の中で最大のものを見つける関数を定義しなさい。
問題８：上記において最小のものを見つける関数を定義しなさい。
問題９：与えられた木構造の要素(ノード)は加算が可能な型である。そこで、すべての要素の和を求める関数を定義しなさい。
問題１０：スポーツや勝負事の世界で用いられるトーナメントは二分木の例である。そこで、(直下がEmptyTreeになっている)末端のノードには選手の名前が、そうでないノードには、その直下のノードの選手同士が戦った時の勝者の名前が入るようにしたい。あるトーナメント試合の結果を木構造で表しなさい。
