OCaml 入門その2  リスト・ヴァリアント・パターンマッチ

[その1](https://qiita.com/zenwerk/items/3bdf7eef6b7511e11b2c)

## リスト
再帰的多層的データ構造。

型名は **型 list**

```ocaml
# [1;2;3;4;5];;
- : int list = [1; 2; 3; 4; 5]
# ["a"; "b"; "c"];;
- : string list = ["a"; "b"; "c"]

(* 異なる型は同じリストに入らない *)
# [1; "a"];;
Error: This expression has type string but an expression was expected of type int
```

### リストの先頭に値を追加する
コンスオペレータ (**::**) を使う。
右結合

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

(* 右結合 *)
# 1 :: 2 :: [3; 4];;
- : int list = [1; 2; 3; 4]
```

### リストの結合
**@** を使う。

```ocaml
# [] @ [];;
- : 'a list = []
# [1] @ [2; 3];;
- : int list = [1; 2; 3]
# ["asdf"; "hoge"] @ ["fuga"];;
- : string list = ["asdf"; "hoge"; "fuga"]
```

## パターンマッチ

### match式

**match 式 with パターン1 -> 式 | パターン2 -> 式 ...**

#### 整数リストの合計を求める例
```ocaml
# let rec total l =
    match l with
      [] -> 0
    | h :: rest -> h + (total rest);;
val total : int list -> int = <fun>
# total [1; 2; 3; 4; 5];;
- : int = 15
```

#### リストを反転する関数の例
```ocaml
# let reverse l =
    let rec innerReverse l1 l2 =
      match l1 with
      | [] -> l2
      | h :: rest -> innerReverse rest (h :: l2)
    in
    innerReverse l [];;
val reverse : 'a list -> 'a list = <fun>
# reverse [1; 2; 3; 4];;
- : int list = [4; 3; 2; 1]
```

### function 式
`fun` と `match` を組み合わせて匿名関数を定義する。

**function パターン1 -> 式 | パターン2 -> 式 ...**

前項の `total` は以下のように書き直せる。
最後の引数でパターンマッチングを行い、その引数をパターンマッチにしか使わないときに便利。

```ocaml
# let rec total = function
    [] -> 0
  | h :: rest -> h + (total rest);;
val total : int list -> int = <fun>
# total [1; 2; 3; 4; 5];;
- : int = 15
```

#### map関数の例
```ocaml
# let rec map fn = function
    | [] -> []
    | h :: rest -> fn h :: map fn rest;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
# map (fun x -> x + 1) [1; 2; 3; 4];;
- : int list = [2; 3; 4; 5]
```

#### fold(畳み込み)の例
```ocaml
(* 左畳み込み *)
# let rec foldl fn acc l =
    match l with
    | [] -> acc
    | h :: rest -> foldl fn (fn acc h) rest;;

(* リストの長さを求める畳み込みの例 *)
# foldl (fun acc x -> acc + 1) 0 [1; 2; 3];;
- : int = 3

(* 右畳み込み *)
# let rec foldr fn l acc =
    match l with
    | [] -> acc
    | h :: rest -> fn h (foldr fn rest acc);;
val foldr : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
```

### パターンマッチのガード節
**match 式 with パターン1 when 真偽式 -> 式 | ...**
`when` を使う。

### 注意: match, function には終わり記号がない
`match with` と `function` には終わりを示す記号がない。
そのため、パターンマッチが入れ子だったりする場合は `()` などを使って囲む必要がある。

## データ構造

### レコード (record)
C言語での構造体、Pythonの辞書に相当するデータ構造。
要素名に名前を付ける。

#### レコードの定義
**type 型名 = {フィールド名: 型; ...}**
`フィールド` -> 名前と値の組

フィールド名は他のレコードと重複使用できないので注意。

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

#### レコードの作成
**{フィールド名 = 値; ...}**

```ocaml
# let s = {name = "hoge"; id = 1};;
val s : student = {name = "hoge"; id = 1}
```

#### レコードの流用
既存の値の上書きではなく、新たなレコード値を作成する。
**{レコード with フィールド名 = 値; ...}**

```ocaml
# let s2 = {s with name = "fuga"};;
val s2 : student = {name = "fuga"; id = 1}
```

### ヴァリアント
場合分けを表すデータ構造。

```ocaml
type 型名 =
  | コンストラクタ [ of <type> [* <type>]... ]
  | コンストラクタ [ of <type> [* <type>]... ]
  | ...
```

- コンストラクタは英語大文字から始める
- `of` 移行はコンストラクタに必要な引数の型
	- `of int * int` の引数は **intの組ではなく、int を２つ**
	- `of (int * int)` の引数は **intの組** 

4種類の図形を表すヴァリアントの例

```ocaml
# type figure =
  | Point
  | Circle of int
  | Rectangle of int * int (* 引数はint2つ not 組 *)
  | Square of int;;
type figure = Point | Circle of int | Rectangle of int * int | Square of int

# let c = Circle 4;;
val c : figure = Circle 4
# let figs = [Point; Rectangle (1, 1); c];;
val figs : figure list = [Point; Rectangle (1, 1); Circle 4]
```

#### ヴァリアントによるパターンマッチ
**function | コンストラクタ 引数 -> | ...**

引数部分を省略すると、引数なしコンストラクタを意味する。

```ocaml
(* 図形の面積を計算する例 *)
# let area = function
  | Point -> 0
  | Circle r -> r * r * 3
  | Rectangle (x, y) -> x * y
  | Square x -> x * x;;
val area : figure -> int = <fun>
# area c;;
- : int = 48
```

#### 多相的なヴァリアント型
型変数(`'a`など)をつかったヴァリアント型の定義が可能
パラメータつきヴァリアントととも呼ぶ。

例えば `'a list` を多相的なヴァリアントを使って表現することができる。

```ocaml
# type 'a mylist =
  | Nil
  | Cons of 'a * 'a mylist;;
type 'a mylist = Nil | Cons of 'a * 'a mylist
# Nil;;
- : 'a mylist = Nil

(* 整数リストを表現 *)
# Cons(1, Nil);;
- : int mylist = Cons (1, Nil)

(* 文字リストを表現 *)
# Cons('a', Cons('b', Nil));;
- : char mylist = Cons ('a', Cons ('b', Nil))
```

##### Optional
俗に言うオプショナル。値がない場合があることを示す。

```ocaml
# type 'a option =
  | None
  | Some of 'a;;
type 'a option = None | Some of 'a
```

オプショナルを利用した例

```ocaml
# let fact n =
    let rec fact' n = if n = 0 then 1 else n * fact' (n - 1) in
    if n < 0 then None else Some (fact' n);;
val fact : int -> int option = <fun>
# fact 3;;
- : int option = Some 6
# fact (-10);;
- : int option = None
```

#### 再帰ヴァリアント型
コンストラクタの `of` 以下に自身の型が出現するヴァリアント型。

##### 二分木の例

```ocaml
# type 'a btree =
  | Leaf
  | Node of 'a * 'a btree * 'a btree;;
type 'a btree = Leaf | Tree of 'a * 'a btree * 'a btree

# Node(1, Node(1, Leaf, Leaf), Node(1, Node(1, Leaf, Leaf), Leaf));;
- : int btree =
Node (1, Node (1, Leaf, Leaf), Node (1, Node (1, Leaf, Leaf), Leaf))
```

木の要素数と高さを求める関数例

```ocaml
# let tr = Node(1, Node(1, Leaf, Leaf), Node(1, Node(1, Leaf, Leaf), Leaf));;  
val tr : int btree =
  Node (1, Node (1, Leaf, Leaf), Node (1, Node (1, Leaf, Leaf), Leaf))

(* 高さを求める関数 *)
# let rec height = function
  | Leaf -> 0
  | Node(_, left, right) -> 1 + max (height left) (height right);;
val height : 'a btree -> int = <fun>
# height tr;;
- : int = 3

(* 要素数を求める関数 *)
# let rec size = function
  | Leaf -> 0
  | Node (_, left, right) -> 1 + size left + size right;;
val size : 'a btree -> int = <fun>
# size tr;;
- : int = 4
```

#### 二分探索木の例

- 要素の追加

```ocaml
# let rec insert x = function
  | Leaf -> Node(x, Leaf, Leaf)
  | Node(k, left, right) ->
      if x < k then Node(k, insert x left, right)
      else Node(k, left, insert x right);;
val insert : 'a -> 'a btree -> 'a btree = <fun>
```

- 要素の検索

```ocaml
# let rec mem x = function
  | Leaf -> false
  | Node(k, left, right) ->
      if x < k then mem x left
      else if x = k then true
      else mem x right;;
val mem : 'a -> 'a btree -> bool = <fun>
```

- 使用例

```ocaml
# let tr = Leaf;;
val tr : 'a btree = Leaf
# tr;;
- : 'a btree = Leaf
# insert 10 tr;;
- : int btree = Node (10, Leaf, Leaf)
# let tr = insert 10 tr;;
val tr : int btree = Node (10, Leaf, Leaf)
# let tr = insert 5 tr;;
val tr : int btree = Node (10, Node (5, Leaf, Leaf), Leaf)
# let tr = insert 20 tr;;
val tr : int btree = Node (10, Node (5, Leaf, Leaf), Node (20, Leaf, Leaf))
# mem 5 tr;;
- : bool = true
# mem 15 tr;;
- : bool = false
```

#### バラの木の例
バラの木とは子の要素数が未定の木。
UNIXのディレクトリ構造と同じものと捉えて良い。

- 型定義

```ocaml
(* 子要素の数は不定なので Node の要素は list *)
# type 'a rosetree = RLeaf | RNode of 'a * 'a rosetree list;;
type 'a rosetree = RLeaf | RNode of 'a * 'a rosetree list
```

##### バラの木としてのXML

- 型定義
	- XMLなので葉にも値があったりなかったり -> (**'b option**)

```ocaml
(* 'a がタグ, 'b が値 *)
# type ('a, 'b) xml = XLeaf of 'b option | XNode of 'a * ('a, 'b) xml list;;
type ('a, 'b) xml = XLeaf of 'b option | XNode of 'a * ('a, 'b) xml list
```

- XMLデータ構造を文字列化する関数
	- 再帰的なXML(バラの木)の中に再帰的なデータ構造であるリストが含まれる
		- 相互再帰的な定義となる

```ocaml
# let rec string_of_xml = function
  | XNode(tag, xml_list) -> "<" ^ tag ^ ">" ^ string_of_xmllist xml_list ^ "</" ^ tag ^ ">"
  | XLeaf None -> ""
  | XLeaf(Some s) -> s
  and
  string_of_xmllist = function
  | [] -> ""
  | xml :: rest -> string_of_xml xml ^ string_of_xmllist rest;;
val string_of_xml : (string, string) xml -> string = <fun>
val string_of_xmllist : (string, string) xml list -> string = <fun>
```

#### 無限列
整数の無限列の例

```ocaml
# type intseq = Cons of int * (int -> intseq);;
type intseq = Cons of int * (int -> intseq)
```

- インクリメントされる無限列の例

```ocaml
# let rec f x = Cons(x+1, f);;
val f : int -> intseq = <fun>
# f 0;;
- : intseq = Cons (1, <fun>)
# f 100;;
- : intseq = Cons (101, <fun>)
```

- 返り値の`x` が `次の要素`
	- `x` を引数に与えることでシーケンスに要素を取得していく

```ocaml
# let Cons(x, f) = f 0;;
val x : int = 1
val f : int -> intseq = <fun>
# let Cons(x, f) = f x;;
val x : int = 2
val f : int -> intseq = <fun>
# let Cons(x, f) = f x;;
val x : int = 3
val f : int -> intseq = <fun>
```

- N番目の要素を取得する関数

```ocaml
# let rec nthseq n (Cons(x, f)) =
    if n = 1 then x
    else nthseq (n-1) (f x);;
val nthseq : int -> intseq -> int = <fun>
# nthseq 10 (f 0);;
- : int = 10
```

## 参考文献
![](http://image.gihyo.co.jp/assets/images/cover/2007/9784774132648.jpg)

[プログラミング in OCaml](http://gihyo.jp/book/2007/978-4-7741-3264-8)

非常に分かりやすく、OCamlを学ぶ際にオススメです。