OCaml『プログラミングの基礎』勉強メモ（後編）

前編はこちら: OCaml『プログラミングの基礎』勉強メモ（前編） - Qiita

15章: 新しい形の再帰

let take n lst p = filter (fun item -> p item n) lst

(* quick_sort : int list -> int list *)
let rec quick_sort lst = match lst with
    [] -> []
  | x::xs -> quick_sort (take x xs (<))
             @ [x]
             @ quick_sort (take x xs (>))

@はリストの結合.

ここで使ったquick_sort再帰はリストを減らして回すというような構造的再帰ではなく"一般の再帰". これは停止性が自明ではない. 停止性を示すには

1. 再帰呼び出しを行う際の部分問題が, 何らかの意味で元の部分より簡単になっていること
2. それを繰り返すと, 有限回で自明なケースに帰着されること

の2点を示せば良い.

16章: 情報の蓄積

結果をresultに入れて引き回すタイプの再帰

let reverse lst =
  let rec rev lst result = match lst with
      [] -> result
    | x::xs -> rev xs (x::result)
  in rev lst [];;
(* val reverse : 'a list -> 'a list = <fun> *)

reverse [1; 2; 3; 4];;
(* - : int list = [4; 3; 2; 1] *)

17章: 再帰的なデータ構造

バリアント型

type team_t = Red | White;;
(* type team_t = Red | White *)
Red ;;   (* - : team_t = Red *)
White ;; (* - : team_t = White *)

RedもしくはWhiteの値を取るバリアント型としてteam_tを定義すると, その後RedもしくはWhiteを評価すればそれでteam_t型とみなされる.

RedやWhiteを「構成子(constructor)」と言う. 構成子は大文字で始まらねばならず大文字は構成子と決まっている.

構成子はパターンマッチに使える. また, 引数を取ることができる.

type jp_t = Meiji of int
          | Taisho of int
          | Showa of int
          | Heisei of int

let to_ad jp_t = match jp_t with
    Meiji  (n) -> n + 1887
  | Taisho (n) -> n + 1911
  | Showa  (n) -> n + 1925
  | Heisei (n) -> n + 1988

to_ad(Meiji(4));;
(* - : int = 1891 *)

木

type tree_t = Empty
            | Leaf of int
            | Node of tree_t * int * tree_t (* cons cell *)

(* Node (Node (Empty, 7, Leaf (3)), 17, Leaf (24));;
   - : tree_t = Node (Node (Empty, 7, Leaf 3), 17, Leaf 24) *)

let rec sum_tree tree = match tree with
    Empty -> 0
  | Leaf (n) -> n
  | Node (left, m, right) -> m + (sum_tree right) + (sum_tree right)

(* sum_tree (Node (Node (Empty, 7, Leaf (3)), 17, Leaf (24)));;
   - : int = 65 *)

つぎに二分探索木を考える. まず, データは次の規則を満たして格納されている二分木.

1. Nodeの左木に格納されているデータは, すべてNode自身に格納されているデータよりも小さい
2. Nodeの右木に格納されているデータは, すべてNode自身に格納されているデータよりも大きい

let rec search tree data = match tree with
    Empty -> false
  | Leaf (m) ->
     if data = m then true else false
  | Node (left, m, right) ->
     if data = m
     then true
     else if data < m (* 検索対象が半分になる *)
          then search left data
          else search right data

let t = (Node (Node (Empty, 2, Leaf (3)), 17, Leaf (24)));;

search t 2;;
search t 10;;

木にデータを入れるinsert_treeの定義

(* val insert_tree : tree_t -> int -> tree_t = <fun> *)
let rec insert_tree tree data = match tree with
    Empty -> Leaf (data)
  | Leaf (n) ->
     if data = n
     then Leaf (n)
     else if data < n
          then Node (Leaf (data), n, Empty)
          else Node (Empty, n, Leaf (data))
  | Node (left, n, right) ->
     if data = n
     then Node (left, n, right) (* 変化なし *)
     else if data < n
          then Node (insert_tree left data, n, right)
          else Node (left, n, insert_tree right data)

insert_tree t 10;;
(* - : tree_t = Node (Node (Empty, 2, Node (Empty, 3, Leaf 10)), 17, Leaf 24) *)

次は, 木の中にint以外のデータを保存できるようにしてみる(多相型の宣言)

type 'a pol_tree_t = Empty
                   | Leaf of 'a
                   | Node of 'a pol_tree_t * 'a * 'a pol_tree_t

Node (Empty, "hoge", Leaf ("fuga"));;
(* - : string pol_tree_t = Node (Empty, "hoge", Leaf "fuga") *)

stringを入れるとstring pol_tree_tになる

18章: 例外と例外処理

NoneもしくはSome of 'aのいずれかを取るoption型というものがあらかじめ定義されている.

None;;
(* - : 'a option = None *)
Some 2;;
(* - : int option = Some 2 *)

Noneによって例外処理もどきが実現可能だが, コードが複雑になるというデメリットがある.
他方, 最近のプログラミング言語には大抵用意されているraise等の例外構文により, コードのきれいな構造を崩すことなく例外処理を行える.

例外の定義: exception
例外発生: raise
例外処理: try ... with

exception Zero

(* リストの数を掛け合わせて行き, 0が見つかったら例外Zeroを発生させて脱出 *)
(* val times : int list -> int = <fun> *)
let times lst =
  let rec mul lst = match lst with
      [] -> 1
    | x::xs ->
       if x = 0 then raise Zero
       else x * mul xs
  in try
    mul lst
  with Zero -> 0

19章: モジュール

モジュール宣言構文

module NAME = struct ... end

木をモジュールで表現

module Tree = struct
  type ('a, 'b) t = Empty
                  | Node of ('a, 'b) t * 'a * 'b * ('a, 'b) t

  let empty = Empty

  let rec insert tree k v = match tree with
      Empty -> Node (Empty, k, v, Empty)
    | Node (left, key, value, right) ->
       if k = key then Node (left, key, v, right)
       else if k < key
       then Node (insert left k v, key, value, right)
       else Node (left, key, value, insert right k v)

  let rec search tree k = match tree with
      Empty -> raise Not_found
    | Node (left, key, value, right) ->
       if k = key then value
       else if k < key then search left k
       else search right k
end


シグネチャ: モジュールの型のようなもの. 木の本質に関わる部分のみ公開し, それ以外はモジュール内部に隠蔽. module typeで作成する.

module type Tree_t = sig
  type ('a, 'b) t
  val empty : ('a, 'b) t
  val insert : ('a, 'b) -> 'a -> 'b -> ('a, 'b) t
  val search : ('a, 'b) -> t -> 'a -> 'b
end

JavaのInterfaceのようなものか? 評価結果は以下のようになる.

(*
module Tree : sig
  type ('a, 'b) t = Empty | Node of ('a, 'b) t * 'a * 'b * ('a, 'b) t
  val empty : ('a, 'b) t
  val insert : ('a, 'b) t -> 'a -> 'b -> ('a, 'b) t
  val search : ('a, 'b) t -> 'a -> 'b
end
*)

「まずmoduleを宣言し, 次にsignatureを制限する」という作り方以外に, いっぺんにやる方法もある. 以下のようにmodule Name : sig ... end = struct ... endとやるか,

module Tree : sig
  (* tree.mli *)
end = struct
  (* tree.ml *)
end

.mliという拡張子でsignatureの内容を定義してやるかのどちらか. OCamlMakefileをつかってMakefileに必要な情報を記述すると, make top で実行ファイル.topが出来る.

20章: モジュールの開発

二分木は仮にデータが偏ってたら(片側の木が常にEmptyだったら)バランスが悪く, 検索効率が悪くなってしまう. そこでバランスを取ったバランス木と呼ばれるデータ構造が出て来て, 一例として赤黒木(red-black tree)を取り上げる. これは

1. rootからEmptyな木に至るすべてのパスにおいて黒い頂点の数は同じ
2. 赤い頂点の子はどちらも必ず黒である(= 赤い頂点が連続することはない)

という2点を満たすデータ構造.

21章: 逐次実行

副作用のある関数

副作用とは「入力に対して結果を返す」以外の働きのこと.
OCamlにおける「何も返さない」ことはunit型で表し, unit型の唯一の値は()である. ()はユニットと読む.

# ();;
- : unit = ()

# print_string "asdf\n" ;;
asdf
- : unit = ()

print_string ;;
- : string -> unit = <fun>

print_string関数はstringを受け取りunitを返す.

上でprint_stringと書くと関数の情報を返すだけで, Rubyのようにメソッド呼び出しとはならない. 引数省略不可. じゃあ引数のない関数はどうする? => unitを受け取る.

print_newline ;;
- : unit -> unit = <fun>

# print_newline () ;;

- : unit = ()

逐次実行

(exp; exp; exp; ... exp;)と書くと各式を実行して結果を捨て, 実行して捨て...を繰り返して最後の式の結果だけを全体の返り値とする. これを逐次実行と言う. 途中の結果は捨てられるので唯一の意味ある使い方は副作用のある, 返り値がunitである式.

let rec gcd m n =
  (print_string "m = ";
   print_int m;
   print_string "n = ";
   print_int n;
   print_newline ();
  if n = 0 then m
           else gcd n (m mod n))

# gcd 216 126;;
m = 216n = 126
m = 126n = 90
m = 90n = 36
m = 36n = 18
m = 18n = 0
- : int = 18

副作用を持つ関数を使うようになると実行順序によって結果が違ってくる. OCamlはインタプリタ/コンパイラの実装の都合上, 式を「右から」順に実行する.

実行順序を意識する必要があるプログラムは良いプログラムではない.

スタンドアローンのプログラム

$ curl -L -O https://raw.githubusercontent.com/mmottl/ocaml-makefile/master/OCamlMakefile

$ cat Makefile
SOURCES = fac.ml main.ml
RESULT = fac
OCAMLMAKEFILE = OCamlMakefile
include $(OCAMLMAKEFILE)

引数を受け取って階乗を返すプログラムを作る.

fac.ml

let rec f n =
  if n = 0 then 1 else n * f (n-1)

main.ml

let main n =
  let result = Fac.f n in
    print_int result

let _ = main (int_of_string Sys.argv.(1))

$ make
$ ./fac 10
3628800

22章: 値の書き変えと参照透過性

基本的には参照透過性を維持してプログラムを書いたほうがわかりやすいので良い. が, 実行回数のカウンターなどあえて参照透過性を破ったほうが良い場合もある. 変更可能なデータを作るにはrefを使い, 値を取得するには!, 書き換える場合は:=を使う.

(* Referential transparency *)
let count = ref 0;;
let rec fib n =
  (count := !count + 1;
   if n < 2 then n else fib (n - 1) + fib (n - 2))

# !count;;
- : int = 0
# fib 10;;
- : int = 55
# !count;;
- : int = 177

配列

リスト != 配列

[ 1; 2; 3 ];;
- : int list = [1; 2; 3]
[| 1; 2; 3 |];;
- : int array = [|1; 2; 3|]

arrayは Array.get a 2 または a.(2) とindexでアクセスできる. またarrayはもともとmutableであり, Array.set a 1 7 や a.(1) <- 7 でデータを変更できる.

23章: 副作用命令を使ったプログラミング

ヒープ

ヒープは木構造の一種. n個のデータが入っている場合データの取得はnに関わらず定数時間, 更新はlognでできるようなデータ構造. ソート条件は

親の値がどちらの子の頂点の値よりも小さい

こと. また, ヒープは中で副作用のある命令を使うため値の参照透過性がないことに注意.