カテゴリー: OCaml

多相的関数が型情報をパラメータ化できるのと同じように，ヴァリアントの定義の一部をパラメータ化することができる。

# type 'a mylist = Nil | Cons of 'a * 'a mylist;;
type 'a mylist = Nil | Cons of 'a * 'a mylist

‘a がパラメータ化された部分。このヴァリアントは Cons の引数にどんな型でも取ることができる。たとえば整数：

# let n1 = Cons (1, Nil);;
val n1 : int mylist = Cons (1, Nil)
# let n2 = Cons (2, n1);;
val n2 : int mylist = Cons (2, Cons (1, Nil))

文字列でも：

# let s1 = Cons ("a", Nil);;
val s1 : string mylist = Cons ("a", Nil)
# let s2 = Cons ("b", s1);;
val s2 : string mylist = Cons ("b", Cons ("a", Nil))

type宣言において，コンストラクタの引数に今宣言しようとしているヴァリアントを使うことができる。つまり再帰的な宣言。

以下は0を含む自然数（というか正の整数）を表す型 nat を宣言する例。

• ゼロは自然数である
• 自然数より1大きい数は自然数である

これをヴァリアントとして宣言すると：

# type nat = Zero | OneMoreThan of nat;;
type nat = Zero | OneMoreThan of nat

そのままだね。

これを使って足し算を定義するとこうなる：

# let rec add m n =
match m with
Zero -> n
| OneMoreThan m' -> OneMoreThan (add m' n)
;;
val add : nat -> nat -> nat = <fun>

• ゼロにnを足した数はnである
• m’より1大きい数にnを足した数はm’とnを足した数より1大きい数である

これもそのまんま。

実際に計算してみよう。

# let zero = Zero;;
val zero : nat = Zero
# let one = OneMoreThan zero;;
val one : nat = OneMoreThan Zero
# let two = OneMoreThan one;;
val two : nat = OneMoreThan (OneMoreThan Zero)
# add zero one;;
- : nat = OneMoreThan Zero
# add one one;;
- : nat = OneMoreThan (OneMoreThan Zero)
# add one one = two;;
- : bool = true

引数をとらないコンストラクタのみでヴァリアントを作れば，いわゆる列挙型になる。

# type color =
Black
| Blue
| Red
| Magenta
| Green
| Cyan
| Yellow
| White
;;
type color = Black | Blue | Red | Magenta | Green | Cyan | Yellow | White

コンストラクタの名前は：

• 一文字目が大文字
• 二文字目以降が英数字（A..Z, a..z, 0..9），アンダースコア（_）またはプライム（’）

であるような任意の長さの文字列。

type 宣言を使って宣言できるデータにはヴァリアントというのもある。おおざっぱに言うと「作り方に何種類か方法があるようなデータ」。Haskellでいう代数的データ型と同じと思っていいのかな。

たとえば次のようなものがヴァリアント。

# type figure =
Point
| Circle of int
| Rectangle of int * int
| Square of int
;;
type figure = Point | Circle of int | Rectangle of int * int | Square of int

figure は図形を表すヴァリアントで，Point，Circle，Rectangle，Square をコンストラクタといい，ここではそれぞれ点，円，長方形，正方形を表している。コンストラクタはヴァリアントの値を作るのに使われる。

of に続くのはそれぞれの図形の大きさを表すための型（ここではすべて整数にしてある)。

ヴァリアントの値は，コンストラクタを（関数のように）適用することで作ることができる。

# let c = Circle 3;;
val c : figure = Circle 3
# let r = Rectangle (3,4);;
val r : figure = Rectangle (3, 4)

ただ，Rectangle のようにタプルをとるように見えるコンストラクタでも，別のところで作ったタプルに適用することはできない。

# let p = (2, 5);;
val p : int * int = (2, 5)
# let r2 = Rectangle p;;
Characters 9-20:
let r2 = Rectangle p;;
^^^^^^^^^^^
The constructor Rectangle expects 2 argument(s),
but is here applied to 1 argument(s)

Point，Circle，Rectangle，Square はどれも figure 型なので，一つにリストに入れることができる。

# let figs = [Point; c; r; Square 5];;
val figs : figure list = [Point; Circle 3; Rectangle (3, 4); Square 5]

もちろん関数でもひとまとめに扱える。それぞれのコンストラクタで扱いが違うときには，パターンマッチング（ヴァリアントパターン）を使う。

# let area_of_figure = function
Point -> 0
| Circle r -> r * r * 3
| Rectangle (x, y) -> x * y
| Square x -> x * x
;;
val area_of_figure : figure -> int = <fun>
# area_of_figure c;;
- : int = 27
# area_of_figure r;;
- : int = 12
# List.map area_of_figure figs;;
- : int list = [0; 27; 12; 25]

レコードの型を宣言するときの注意。既存の型と同じフィールド名を使ってしまうと，先に宣言した型のフィールド名が使えなくなってしまう。たとえば前エントリの student とその値が存在している状態で：

# type student = {name : string; id : int};;
type student = { name : string; id : int; }
# let st1 = {name = "Taro"; id = 123};;
val st1 : student = {name = "Taro"; id = 123}
# let st2 = {id = 51; name = "Ichiro"};;
val st2 : student = {name = "Ichiro"; id = 51}

新しいレコードの型を宣言する。フィールド名 name が重なっている。

# type foo = {name : bool};;
type foo = { name : bool; }

すると，name は foo のフィールド名としては使えるけど，student のフィールド名としては使えなくなってしまう。

# let f1 = {name = true};;
val f1 : foo = {name = true}
# let st4 = {name = "Daisuke"; id = 16};;
Characters 18-27:
let st4 = {name = "Daisuke"; id = 16};;
^^^^^^^^^
This expression has type string but is here used with type bool

アクセスもできない。

# st2.name;;
Characters 0-3:
st2.name;;
^^^
This expression has type student but is here used with type foo

f1 のフィールドにはアクセスできる。

# f1.name;;
- : bool = true

レコードとはいくつかの値に名前を付けてまとめて扱えるようにしたデータ。構造体のようなもの。名前と値をあわせてフィールド，名前をフィールド名と呼ぶ。

新しいレコードの型を宣言するには type 宣言を使う。

# type student = {name : string; id : int};;
type student = { name : string; id : int; }

name と id がフィールド名でそれぞれの値の型が string と int だ。

レコードを作るには次のようにする。フィールドの順番は入れ替わってもok。

# let st1 = {name = "Taro"; id = 123};;
val st1 : student = {name = "Taro"; id = 123}
# let st2 = {id = 51; name = "Ichiro"};;
val st2 : student = {name = "Ichiro"; id = 51}

また，すでにあるレコードと一部だけが違うレコードを作る方法もある。

# let st3 = {st1 with id = 456};;
val st3 : student = {name = "Taro"; id = 456}

st1 のフィールドを書き換えるわけではないことに注意。

# st1;;
- : student = {name = "Taro"; id = 123}

レコードのフィールドを参照するにはドット記法が使える。

# st2.name;;
- : string = "Ichiro"
# st2.id;;
- : int = 51

また，パターンマッチングもできる。

# let string_of_student {name = n; id = i} =
n ^ "'s ID is " ^ string_of_int i
;;
val string_of_student : student -> string = <fun>
# string_of_student st2;;
- : string = "Ichiro's ID is 51"

パターンにはすべてのフィールドを列挙する必要はなく，一部でもいい。

# let name_of_student {name = n} = n ;;
val name_of_student : student -> string = <fun>
# name_of_student st1;;
- : string = "Taro"

5. 2つの[a1; …; an] と [a1; …; bn] を引数として，[(a1,b1); …; (an,bn)] を返す関数 zip （与えられたリストの長さが異なる場合は長いリストの余った部分を捨ててよい）。

# let rec zip l1 l2 =
match (l1, l2) with
([], _) -> []
| (_, []) -> []
| (h1::t1, h2::t2) -> (h1, h2) :: zip t1 t2
;;
val zip : 'a list -> 'b list -> ('a * 'b) list = <fun>
# zip [2; 3; 4; 5; 6; 7; 8; 9; 10; 11]
[true; true; false; true; false; true; false; false; false; true];;
- : (int * bool) list =
[(2, true); (3, true); (4, false); (5, true); (6, false); (7, true);
(8, false); (9, false); (10, false); (11, true)]

6. ペアのリスト [(a1,b1); …; (an,bn)] を引数として，リストのペア ([a1; …; an], [b1; …; bn]) を返す関数 unzip。

# let unzip l = (List.map fst l, List.map snd l);;
val unzip : ('a * 'b) list -> 'a list * 'b list = <fun>
# unzip (zip [2;3;4;5;6;7;8;9;10;11]
[true; true; false; true; false; true;
false; false; false; true]);;
- : int list * bool list =
([2; 3; 4; 5; 6; 7; 8; 9; 10; 11],
[true; true; false; true; false; true; false; false; false; true])

7. リストと，リストの要素上の述語 p を満たすすべての要素のリストを返す関数 filter。

# let rec filter p = function
[] -> []
| hd::tl when p hd -> hd :: filter p tl
| hd::tl           -> filter p tl
;;
val filter : ('a -> bool) -> 'a list -> 'a list = <fun>
# filter (fun l -> List.length l =3) [[1;2;3]; [4;5]; [6;7;8]; [9]];;
- : int list list = [[1; 2; 3]; [6; 7; 8]]

8. 先頭からn番目までの要素からなる部分リストを取り出す関数 take とn番目までの要素を抜かした 部分リストを取り出す drop。

まず take。

# let rec take n = function
[] -> []
| hd::tl -> if n = 0 then [] else hd :: take (n-1) tl
;;
val take : int -> 'a list -> 'a list = <fun>
# take 3 [1;2;3;4;5];;
- : int list = [1; 2; 3]
# take 0 [1;2;3;4;5];;
- : int list = []

drop。

# let rec drop n = function
[] -> []
| hd::tl -> if n = 0 then hd::tl else drop (n-1) tl
;;
val drop : int -> 'a list -> 'a list = <fun>
# drop 3 [1;2;3;4;5];;
- : int list = [4; 5]
# drop 0 [1;2;3;4;5];;
- : int list = [1; 2; 3; 4; 5]

9. （空でない）リストの中から最大値を返す関数 max_list。

# let max_list l =
let hd::tl = l in
List.fold_left max hd tl
;;
Characters 25-31:
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
let hd::tl = l in
^^^^^^
val max_list : 'a list -> 'a = <fun>
# max_list [5; 9; 0; -7];;
- : int = 9

警告がでてるのは空リストに対応できてないからだろう。まぁ問題の答えにはなってるのでいいことにする。

次の関数を定義しなさい。

1. 正の整数 n から 1 までの整数の降順リストを生成する関数 downto1。

# let rec downto1 n = if n = 0 then [] else n :: downto1 (n-1);;
val downto1 : int -> int list = <fun>
# downto1 6;;
- : int list = [6; 5; 4; 3; 2; 1]

2. 与えられた正の整数のローマ数字表現を求める関数 roman。ただし，roman は単位となる 数とローマ数字表現の組を大きいものから並べたリストで表現した，ローマ数字の定義も引 数として受け取ることにする。

# let roman r n =
let rec iter_string n s = if n = 0 then "" else s ^ iter_string (n-1) s in
let roman' num rom =
let (n, s) = num in
let (rn, rs) = rom in
(n mod rn, s ^ iter_string (n / rn) rs)
in
snd (List.fold_left roman' (n, "") r)
;;
val roman : (int * string) list -> int -> string = <fun>
# roman [(1000,"M");(500,"D");(100,"C");(50,"L");(10,"X");(5,"V");(1,"I")] 1984;;
- : string = "MDCCCCLXXXIIII"

また，900，400，90，40，9，4 の表現を変えると

# roman [(1000,"M");(900,"CM");(500,"D");(400,"CD");(100,"C");(90,"XC");(50,"L");(4 0,"XL");(10,"X");(9,"IX");(5,"V");(4,"IV");(1,"I")] 1984;;
- : string = "MCMLXXXIV"

3. 与えられたリストのリストに対し，（内側のリストの）要素の総数を返す関数 nested_le ngth。

# let nested_length l = List.length (List.concat l);;
val nested_length : 'a list list -> int = <fun>
# nested_length [[1;2;3]; [4;5]; [6]; [7;8;9;10]];;
- : int = 10
# nested_length [[1;2;3]; [4;5]; []; [6;7;8;9]];;
- : int = 9

次の 4. を見て気がついた。もしかして List.concat は使っちゃだめだったのか？

# let nested_length l = List.fold_left (fun x y -> x + List.length y) 0 l;;
val nested_length : 'a list list -> int = <fun>
# nested_length [[1;2;3]; [4;5]; [6]; [7;8;9;10]];;
- : int = 10

4. 与えられたリストのリストに対し，内側のリストの要素を並べたリストを返す関数 concat。

# let concat l = List.fold_left (fun x y -> x @ y) [] l;;
val concat : '_a list list -> '_a list = <fun>
# concat [[1;2;3];[4;5];[6];[7;8;9;10]];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

もしかして List.fold_left も使わないのかな。なら再帰で。

# let rec concat' = function
[] -> []
| hd::tl -> hd @ concat' tl
;;
val concat' : 'a list list -> 'a list = <fun>
# concat' [[1;2;3]; [4;5]; [6]; [7;8;9;10]];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Haskell で一番有名（？）なコードを OCaml で書いてみた。

# let rec qsort = function
[] -> []
| hd::tl -> qsort (List.filter (fun x -> x < hd) tl) @ [hd] @ qsort (List.filter  (fun y -> hd <= y) tl)
;;
val qsort : 'a list -> 'a list = <fun>
# qsort [1;5;3;2;6;7;4;9];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 9]

はじめ List.filter に与える関数を (>hd) みたいに書いたらだめだった。 OCaml ではセクションは使えないらしい。演算子を関数的に使って部分適用ならok。

# let rec qsort' = function
[] -> []
| hd::tl -> qsort' (List.filter ((>) hd) tl) @ [hd] @ qsort' (List.filter ((<=) hd) tl)
;;
val qsort' : 'a list -> 'a list = <fun>
# qsort' [1;5;3;2;6;7;4;9];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 9]