人気ブログランキング | 話題のタグを見る

Haskell でユーザ定義のデータ型を作る。

Haskell ではユーザ定義のデータ型を作ることができる。ただの二分木 -- 葉には何もデータが登録されないただの枝別れ -- を表現するだけのデータ型を作ってみよう。このタイプのデータ型を DumbTree という名前で作成する。具体的には Hugs からエディターを立ち上げて、次のデータ定義を入力する。

Hugs> :e dumbtree.hs

(dumbtree.hs の内容)
data DumbTree = Empty | Fork DumbTree DumbTree

この定義では、DumbTree 型のデータは二分木のノードの状態を表している。ノードに何の枝もつながっていない場合は、Empty 値をとり、ノードに枝がつながっている場合は Fork 値をとる。Fork はさらに二つのデータフィールドを持っており、第1のフィールドにはノードから左につながっている枝の状態値、第2のフィールドにはノードから右につながっている枝の状態値が収められる。これから分かるように DumbTree 値は二文木の状態に対応する木構造を形作ることになる。

そこで、ファイルを閉じて、:l コマンドでファイルをロードしてデータを作ろうとするとエラーが出る。

Hugs> :l dumbtree.hs
Main> Fork Empty Empty
ERROR - Cannot find "show" function for:
*** Expression : Fork Empty Empty
*** Of type : DumbTree

これは、データの内容を表示するための show 関数が DumbTree 型を認識しないからだ。show 関数でデータを表示させるためには、Show クラスに DumbTree タイプを登録し、show 関数を定義しなければならない。dumbtree.hs に DumbTree 型を Show クラスに登録するプログラムを付け加える。型のクラスの定義を説明するのは大変だが、DumbTree 型がShowクラスに登録されていると、show メソッドが使えるようになると考えればいい。ただ、show 関数は DumbTree 用のものをオーバーライドして定義しなくてはならない。Rubyのスーパークラスのようなものと考えればわかりやすい。

Hugs> :e dumbtree.hs

(dumbtree.hs の内容)
data DumbTree = Empty | Fork DumbTree DumbTree

instance Show DumbTree where
    show Empty = "0"
    show (Fork l r) = "(" ++ show l ++ "^" ++ show r ++ ")"

上のプログラムで instance 宣言の Show は、大文字で始まりクラスを表し、関数の show は小文字で始まるのに注意する必要がある。プログラムの意味は、DumbTree 型は、Show クラスのインスタンスで、show 関数の定義ではEmptyの時は0を表示し、Forkの時はひだりの腕と右の腕の状態の間に分岐のしるしである ^ を表示する。show の定義も再帰的になっているので、結局あるノードから下の全分岐が表示されることになる。

これを再ロードしDumbTree 型のデータを作ってみる。

Main> :r
Main> Empty
0
Main> Fork Empty Empty
(0^0)

うまくいったようだ、そこで、DumpTree 型を使った関数を作ってみる。

Main> merge Empty (Fork Empty Empty) where merge l r = Fork l r
(0^(0^0))

大成功。これで、ユーザー定義データの概要が分かったので、ユーザ定義を使ったサンプルプログラムを読みこなすことができる。Haskell の場合はプログラム例の一部を取り出して実験してみることができる。プログラム例の意味が分かりづらい時は、一部を取り出してこのようにして実験してみるとデータの内容が視覚化できて理解がしやすくなる。

まだ、Haskell に慣れていないのでわからないが、この例のような再帰的な定義の場合は、データ構造はリスト構造や、木構造になるのではないだろうか。ユーザ定義のデータ型は、大まかに列挙型、構造体型、共用体型、リスト型、木構造型になると思われる。木構造型の実装を考えることなく、一行の定義で済んでしまうのが不思議だ。

ユーザ定義のデータに show 関数が必須というわけではないだろうが、これを設定しておくとデータの内容が可視化されるので理解しやすい。最初のうちは、show関数はできるだけ定義しておいたほうがいいだろう。
by tnomura9 | 2009-08-10 07:55 | Haskell | Comments(0)
<< Haskell のファイルの読... Haskell の入出力 >>