前編はこちら: 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再帰はリストを減らして回すというような構造的再帰ではなく"一般の再帰". これは停止性が自明ではない. 停止性を示すには
- 再帰呼び出しを行う際の部分問題が, 何らかの意味で元の部分より簡単になっていること
- それを繰り返すと, 有限回で自明なケースに帰着されること
の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 *)
つぎに二分探索木を考える. まず, データは次の規則を満たして格納されている二分木.
- Nodeの左木に格納されているデータは, すべてNode自身に格納されているデータよりも小さい
- 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`
木をモジュールで表現
```ocaml
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`で作成する.
````ocaml
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)を取り上げる. これは
- rootからEmptyな木に至るすべてのパスにおいて黒い頂点の数は同じ
- 赤い頂点の子はどちらも必ず黒である(= 赤い頂点が連続することはない)
という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である式.
````ocaml
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)
````
引数を受け取って階乗を返すプログラムを作る.
```ocaml:fac.ml
let rec f n =
if n = 0 then 1 else n * f (n-1)
````
```ocaml: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`を使い, 値を取得するには`!`, 書き換える場合は`:=`を使う.
`````ocaml
(* 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でできるようなデータ構造. ソート条件は
> 親の値がどちらの子の頂点の値よりも小さい
こと. また, ヒープは中で副作用のある命令を使うため値の参照透過性がないことに注意.