データ型とパターンマッチング

連結リスト

Perlと同じく、OCamlはリストを言語組込みで提供している。OCamlのリストは、全ての要素が、同じ型をもっていなければならない。リストを書くには、こうする:

# [1; 2; 3];;
- : int list = [1; 2; 3]

(注 セミコロンだ、コンマじゃない)

[]は空のリストだ。

リストには、head(最初の要素) とtail(その残りの要素)がある。head は要素で、tail はリストだ。上の例では、head は整数1で、tail はリスト[2; 3]だ。

別のやりかたでリストを書くには、cons演算子でhead :: tailとやる。なので、以下のやりかたでリストを書いても、まったく一緒だ:

[1; 2; 3]
1 :: [2; 3]
1 :: 2 :: [3]
1 :: 2 :: 3 :: []

どうしてcons演算子に触れたかって?そりゃ、パターンマッチングをリストにやろうってときに便利だからだ。後で説明する。

連結リストの型

整数の連結リストの型は、int listで、一般に、fooの連結リストの型は、foo listである。

ここからわかるように、連結リストの全ての要素は、同じ型でなければならない。しかし、型は多相でもよい(すなわち'a list) これにうってつけなのは、"何かのlist"を扱うような総称関数を、書くときだ。(ただし注意:'a listは、個々の要素が違う型を持つということではない。- リストは、うーん、整数と文字列をごちゃまぜにふくむみたいな、そんなものを作るのには使えない。要素の型は何でもよいが、全部が同じ型でないといけないということだ。)

length関数は、OCamlのListモジュールのところで定義されている。これがよい例だ。リストに入っているのが、整数でも、文字列でも、オブジェクトでも、ちっちゃいふわふわの動物でも、関係なく、List.length関数を呼べばよい。List.lengthの型は、従って、こうなっている:

List.length : 'a list -> int

構造体

CとC++には、単純なstructという概念がある。structure(訳注:構造体)の略だ。Javaにはクラスがあり、これも似たようなことができるうえに、もっといろんな用途もある。

単純なCの構造体を考えよう:

struct pair_of_ints {
  int a, b;
};

OCamlで、これに等価なもので、もっとも簡単なのは、タプル(訳注:組)である。(3, 4)といったもので、型はint * intだ。リストと違って、タプルは違う型の要素を含めるので、例えば、(3, "hello", 'x')とすれば、型はint * string * charだ。

ちょっと難しいが、別のやりかたでCの構造体を書くには、レコードがある。レコードは、Cの構造体みたいに、名前を要素につけることができる。タプルでは、名前を要素につけられないので、かわりに、どこに来るかの順番を覚えておかなければならない。これが、先ほどのCの構造体と等価なレコードだ。

# type pair_of_ints = { a : int; b : int };;
type pair_of_ints = { a : int; b : int; }

これは型を定義している。この型のオブジェクトを実際に作るにはこうする。

# { a=3; b=5 };;
- : pair_of_ints = {a = 3; b = 5}

注 型定義をするときに":"があったところに、この型のオブジェクトを作るときには、"="が入っている。

これは、この型のをトップレベルでやった例だ。:

# type pair_of_ints = { a : int; b : int };;
type pair_of_ints = { a : int; b : int; } # {a=3; b=5};;
- : pair_of_ints = {a = 3; b = 5} # {a=3};;
Error: Some record fields are undefined: b

そう、OCamlは、構造体のフィールドを未定義のままにはさせてくれない。

ヴァリアント (修飾つき共用体と列挙型)

"修飾つき共用体"(原文 "qualified union")はCにはないと言ってよいが、GCCコンパイラは対応している。以下は、修飾つき共用体の、Cでの一般的な使われかたの、見本である:

struct foo {
  int type;
#define TYPE_INT 1
#define TYPE_PAIR_OF_INTS 2
#define TYPE_STRING 3
  union {
    int i;        // If type == TYPE_INT.
    int pair[2];  // If type == TYPE_PAIR_OF_INTS.
    char *str;    // If type == TYPE_STRING.
  } u;
};

こうしてみると、ふつふつと、見ちゃいられないという思いがする。てはじめに、安全じゃない: プログラマーが、ついうっかり、u.iフィー ルドを間違えてしまい、実際には文字列が構造体に入っていた、なんてはめになりそうだ。そのうえ、コンパイラがチェックして、すべての型の可能性が switch文で調べられているかを確かめる、なんてことは、簡単にはできない(かわりに列挙型を使えば、この問題は解消できる)。プログラマーはtypeフィールドをセットし忘れるかもしれない、そうしたら無茶苦茶なことになる。いやがうえにも、厄介だ。

OCamlでは、簡潔に美しく、こうなる。:

# type foo =
    | Nothing
    | Int of int
    | Pair of int * int
    | String of string;;
type foo = Nothing | Int of int | Pair of int * int | String of string

これが型定義だ。|で区切られている。それぞれの区切りの頭のところは、コンストラクタという。呼びやすいものをつければよいが、大文字ではじめること。コンストラクタで、値を定義するときは、続けてof typeの部分がくる。typeはいつも小文字ではじまる。上の例では、Nothingは定数として使われ、他のコンストラクタは、値とともに使われている。

実際にこの型のものを作るには、こう書く。:

Nothing
Int 3
Pair (4, 5)
String "hello"
...

これらの式の各々が、型fooをもつ。

注 型定義を書くときに、ofを使うが、この型の要素を書くときには、使わない。

拡張によって、単純なCの列挙型は、こう定義される:

enum sign { positive, zero, negative };

OCamlではこう書ける:

type sign = Positive | Zero | Negative

再帰ヴァリアント(ツリーに使う)

ヴァリアントは再帰でもよく、ツリー構造を定義するのに普通は使う。これこそが、関数型言語の表現力の、真髄である。:

# type binary_tree =
    | Leaf of int
    | Tree of binary_tree * binary_tree;;
type binary_tree = Leaf of int | Tree of binary_tree * binary_tree

2分木をいくつか用意した。練習に、これらを紙に書き下してみよう。

Leaf 3
Tree (Leaf 3, Leaf 4)
Tree (Tree (Leaf 3, Leaf 4), Leaf 5)
Tree (Tree (Leaf 3, Leaf 4), Tree (Tree (Leaf 3, Leaf 4), Leaf 5))

パラメータつきヴァリアント

前の節の2分木は、おのおのの葉に整数をもっていた、しかし、もし、2分木のカタチを記述したい、葉ノードになにを納めるかは、後で決めたい、というときはどうしたらよいだろうか? こういうときは、パラメータつき(多相)ヴァリアントを使って、こうする。:

# type 'a binary_tree =
    | Leaf of 'a
    | Tree of 'a binary_tree * 'a binary_tree;;
type 'a binary_tree = Leaf of 'a | Tree of 'a binary_tree * 'a binary_tree

これが汎用な型である。整数をおのおのの葉におさめるとき、型の指定は、int binary_treeとなる。同様に、文字列をおのおのの葉におさめるとき、型の指定は、string binary_treeとなる。次の例では、トップレベルで、いくつかのインスタンスに型をつけて、型推論システムに型を示してもらっている。:

# Leaf "hello";;
- : string binary_tree = Leaf "hello" # Leaf 3.0;;
- : float binary_tree = Leaf 3.

どのように型名がさかのぼるかに注意。これを、リスト(例えばint listなど)の型名と、比べてみるとよい。

実は、'a listは同じように"さかのぼる"わけではない。リストはパラメータつきヴァリアント型ではあるが、次のようなちょっと変な定義になっている:

type 'a list = [] | :: of 'a * 'a list   (* not real OCaml code *)

実際には、上の定義でコンパイルされるわけではない。もっと正確な定義は、こうだ:

# type 'a equiv_list =
    | Nil
    | Cons of 'a * 'a equiv_list;;
type 'a equiv_list = Nil | Cons of 'a * 'a equiv_list # Nil;;
- : 'a equiv_list = Nil # Cons(1, Nil);;
- : int equiv_list = Cons (1, Nil) # Cons(1, Cons(2, Nil));;
- : int equiv_list = Cons (1, Cons (2, Nil))

前に、リストは2通りのやりかたで書けるといったことを、思い出してほしい。構文糖で[1; 2; 3]と書けたり、もっと正式には、1 :: 2 :: 3 :: []と書けた。上の'a listの定義を見れば、正式な定義の理由が、きっとわかるだろう。

リスト、構造体、ヴァリアント - まとめ

OCamlでの名前 型定義の例 使用例

リスト          int list                       [1; 2; 3]
タプル          int * string                   (3, "hello")
レコード        type pair =                    { a = 3; b = "hello" }
                 { a: int; b: string }
ヴァリアント    type foo =
                 | Int of int                 Int 3
                 | Pair of int * string
ヴァリアント    type sign =
                 | Positive                   Positive
                 | Zero                       Zero
                 | Negative
パラメータつき  type 'a my_list =
ヴァリアント      | Empty                      Cons (1, Cons (2, Empty))
                 | Cons of 'a * 'a my_list

パターンマッチング(データ型に)

とってもクールな機能が、関数型言語にはある。それは、データ構造をバラして、データにパターンマッチング をする、そんな能力だ。これは、まあ、"関数型"の機能というわけではない。 - どうにかすれば、Cでも、こういったことはできるんじゃないか、とも思える。しかし、これがクールな機能だというのに、変わりはない。

実際のプログラムの仕様をもとに、はじめよう: 単純な数学の式を表現したい。n * (x + y)のような。または、それらの掛け算を記号的に行って、n * x + n * yを得たいのだ。

型の定義を、これらの式についておこなう:

# type expr =
    | Plus of expr * expr        (* means a + b *)
    | Minus of expr * expr       (* means a - b *)
    | Times of expr * expr       (* means a * b *)
    | Divide of expr * expr      (* means a / b *)
    | Value of string            (* "x", "y", "n", etc. *);;
type expr = Plus of expr * expr | Minus of expr * expr | Times of expr * expr | Divide of expr * expr | Value of string

n * (x + y)はこう書かれる:

# Times (Value "n", Plus (Value "x", Value "y"));;
- : expr = Times (Value "n", Plus (Value "x", Value "y"))

出力をする関数を書いて、Times (Value "n", Plus (Value "x", Value "y"))を、もっとこう、n * (x + y)み たいに、書き出すようにしよう。実際には、ふたつの関数を書く。ひとつは、式を変換して、うまく文字列にするもの。ひとつは、それを書き出すもの。 (理由は、同様に文字列をファイルに書き出すものも、書きたいからだ。それだけのために関数まるごとを書きなおすのは避けたい。)

# let rec to_string e =
    match e with
    | Plus (left, right) ->
       "(" ^ to_string left ^ " + " ^ to_string right ^ ")"
    | Minus (left, right) ->
       "(" ^ to_string left ^ " - " ^ to_string right ^ ")"
    | Times (left, right) ->
       "(" ^ to_string left ^ " * " ^ to_string right ^ ")"
    | Divide (left, right) ->
       "(" ^ to_string left ^ " / " ^ to_string right ^ ")"
    | Value v -> v;;
val to_string : expr -> string = <fun> # let print_expr e = print_endline (to_string e);;
val print_expr : expr -> unit = <fun>

(注: \^演算子は、文字列を連結する。)

printの関数を実行するとこうなる:

# print_expr (Times (Value "n", Plus (Value "x", Value "y")));;
(n * (x + y)) - : unit = ()

パターンマッチングの一般的な形はこう:

match value with
| pattern    ->  result
| pattern    ->  result
  ...

左手のpatternは、うえのto_string関数のように、単純かもしれないし、あるいは、複雑で、入れ子かもしれない。次の例で、この関数に、掛け算をいれる。式の形は、n * (x + y)(x + y) * nである。このように、入れ子のパターンを使うことになる。

# let rec multiply_out e =
    match e with
    | Times (e1, Plus (e2, e3)) ->
       Plus (Times (multiply_out e1, multiply_out e2),
             Times (multiply_out e1, multiply_out e3))
    | Times (Plus (e1, e2), e3) ->
       Plus (Times (multiply_out e1, multiply_out e3),
             Times (multiply_out e2, multiply_out e3))
    | Plus (left, right) ->
       Plus (multiply_out left, multiply_out right)
    | Minus (left, right) ->
       Minus (multiply_out left, multiply_out right)
    | Times (left, right) ->
       Times (multiply_out left, multiply_out right)
    | Divide (left, right) ->
       Divide (multiply_out left, multiply_out right)
    | Value v -> Value v;;
val multiply_out : expr -> expr = <fun>

実行するとこうなる。:

# print_expr(multiply_out(Times (Value "n", Plus (Value "x", Value "y"))));;
((n * x) + (n * y)) - : unit = ()

どのようにmultiply_out関数は動いているんだろう? はじめの2つのパターンが鍵だ。1番めのパターンは、Times (e1, Plus (e2, e3))で、e1 * (e2 + e3)のかたちの式にマッチする。この1番めのパターンマッチの右手を見ると、(e1 * e2) + (e1 * e3)なので、等しいことがわかるだろう。

2番めのパターンも、同じことをやっている。ただ、式の形は(e1 + e2) * e3だ。

のこりのパターンは、式の形を変えないが、しかし、重大なことをやっているmultiply_out関数を再帰的に、部分式にたいして呼んでいる。これによって、式のなかの部分式にもすべて、掛け算が行われる。(もし、式の掛け算がただ一段階ですんでいれば、残りのパターンはすべて、単純なe -> eルールに置き換えられただろう。)

逆をやれるだろうか?(すなわち、共通部分式のくくりだし)できるとも!(ただ、もうすこし複雑になる。)以下のバージョンは、一段階の式でしかうまく動かない。改良をすれば、何段階の式でも、より複雑な場合でも、うまくやれるようにできる。:

# let factorize e =
    match e with
    | Plus (Times (e1, e2), Times (e3, e4)) when e1 = e3 ->
       Times (e1, Plus (e2, e4))
    | Plus (Times (e1, e2), Times (e3, e4)) when e2 = e4 ->
       Times (Plus (e1, e3), e4)
    | e -> e;;
val factorize : expr -> expr = <fun> # factorize (Plus (Times (Value "n", Value "x"), Times (Value "n", Value "y")));;
- : expr = Times (Value "n", Plus (Value "x", Value "y"))

上のfactorize関数で、更にまたいくつか、機能が明らかになった。ガードというものを、各パターンマッチにつけたすことができる。 ガードは、条件式で、whenのあとにくる。意味は、パターンマッチが起こるのは、パターンがマッチして、さらにwhen-節の条件が満たされるときだ。

match value with
| pattern  [ when condition ] ->  result
| pattern  [ when condition ] ->  result
  ...

2番目の機能は、=演算子だ。これは、2つの式の間で、"構造的等しさ"をテストする。再帰的におのおのの式に入っていって、そのすべての段階で、ちゃんと同じであるかを調べる。

OCamlは、コンパイル時にチェックをして、パターンのすべての可能性が網羅されているかを確かめてくれる。型定義を変更して、上のtype exprProductヴァリアントを加えてみた:

# type expr = Plus of expr * expr      (* means a + b *)
            | Minus of expr * expr     (* means a - b *)
            | Times of expr * expr     (* means a * b *)
            | Divide of expr * expr    (* means a / b *)
            | Product of expr list     (* means a * b * c * ... *)
            | Value of string          (* "x", "y", "n", etc. *);;
type expr = Plus of expr * expr | Minus of expr * expr | Times of expr * expr | Divide of expr * expr | Product of expr list | Value of string

それから再コンパイルを、to_string関数を変えずにやった。OCamlは以下の警告をしてきた。

# let rec to_string e =
    match e with
    | Plus (left, right) ->
       "(" ^ to_string left ^ " + " ^ to_string right ^ ")"
    | Minus (left, right) ->
       "(" ^ to_string left ^ " - " ^ to_string right ^ ")"
    | Times (left, right) ->
       "(" ^ to_string left ^ " * " ^ to_string right ^ ")"
    | Divide (left, right) ->
       "(" ^ to_string left ^ " / " ^ to_string right ^ ")"
    | Value v -> v;;
Warning 8: this pattern-matching is not exhaustive. Here is an example of a value that is not matched: Product _ val to_string : expr -> string = <fun>