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

(Redirected from ja/data_types_and_matching)

連結リスト

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

[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 };;

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

{ 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};;
Some record field labels 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;;

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

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

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

これらの式の各々が、型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;;

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;;

これが汎用な型である。整数をおのおのの葉におさめるとき、型の指定は、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 list = Nil | :: of 'a * 'a list;;
type 'a list = Nil | :: of 'a * 'a list
# Nil;;
- : 'a list = Nil
# 1 :: Nil;;
- : int list = :: (1, Nil)
# 1 :: 2 :: Nil;;
- : int list = :: (1, :: (2, Nil))

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

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

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


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

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

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
  ;;

let print_expr e =
  print_endline (to_string e);;

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

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

# print_expr (Times (Value "n", Plus (Value "x", Value "y")));;
(n * (x + y))

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

match object 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
  ;;

実行するとこうなる。:

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

どのように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
  ;;
# 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 object 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. *)
          ;;

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

Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Product _