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

その1

リスト

再帰的多層的データ構造。

型名は 型 list

# [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

リストの先頭に値を追加する

コンスオペレータ (::) を使う。
右結合

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

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

リストの結合

@ を使う。

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

パターンマッチ

match式

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

整数リストの合計を求める例

# 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

リストを反転する関数の例

# 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 は以下のように書き直せる。
最後の引数でパターンマッチングを行い、その引数をパターンマッチにしか使わないときに便利。

# 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関数の例

# 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(畳み込み)の例

(* 左畳み込み *)
# 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 型名 = {フィールド名: 型; ...}
フィールド -> 名前と値の組

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

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

レコードの作成

{フィールド名 = 値; ...}

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

レコードの流用

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

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

ヴァリアント

場合分けを表すデータ構造。

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

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

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

# 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 | コンストラクタ 引数 -> | ...

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

(* 図形の面積を計算する例 *)
# 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 を多相的なヴァリアントを使って表現することができる。

# 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

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

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

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

# 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 以下に自身の型が出現するヴァリアント型。

二分木の例

# 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))

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

# 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

二分探索木の例

• 要素の追加

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

• 要素の検索

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

• 使用例

# 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のディレクトリ構造と同じものと捉えて良い。

• 型定義

(* 子要素の数は不定なので 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)

(* '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(バラの木)の中に再帰的なデータ構造であるリストが含まれる
    • 相互再帰的な定義となる

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

無限列

整数の無限列の例

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

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

# 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 を引数に与えることでシーケンスに要素を取得していく

# 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番目の要素を取得する関数

# 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

参考文献

プログラミング in OCaml

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