LoginSignup
14
7

More than 5 years have passed since last update.

@zenwerkinツキノワ株式会社

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

Last updated at Posted at 2017-11-27

その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を学ぶ際にオススメです。

14
7
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
7