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

環境構築

Ubuntu

$ sudo apt-get install ocaml-nox

noxは「without X」, GUIがらみのライブラリがないことを意味するぽい

Emacs

ocaml-modeは微妙という評価を見かけたのでtuareg-modeを使う. いまのところ問題なく使えている
C-c C-rでregionをOCaml REPL(トップレベル)バッファ中で評価してくれるので便利

目次

 1. はじめに
 2. 基本的なデータ
 3. 変数の定義
 4. 関数の定義
 5. 条件分岐
 6. さまざまなエラー
 7. 組とパターンマッチ
 8. レコード
 9. リスト
10. 再帰関数を使ったプログラミング
11. 自然数と再帰
12. ダイクストラのアルゴリズム
13. 一般化と高階関数
14. 高階関数を使ったリスト処理
15. 新しい形の再帰
16. 情報の蓄積
17. 再帰的なデータ構造
18. 例外と例外処理
19. モジュール
20. モジュールの開発
21. 逐次処理
22. 値の書き変えと参照透明性
23. 副作用命令を使ったプログラミング
24. まとめ -- プログラミングとは --

1章: はじめに

基本操作

ocamlコマンドでOCamlのトップレベル(REPL)が起動. 終了するには#quit;;を実行

shell $ ocaml
# "hoge";;
- : string = "hoge"
# #quit;;

# (3. +. 4.);;
- : float = 7.
# (3. + 4.);;
Error: This expression has type float but an expression was expected of type
         int

演算子にも.が必要とな. なんか気持ち悪い

# 2.0 * 3.14;;
Error: This expression has type float but an expression was expected of type
         int
# 2.0 *. 3.14 ;;
- : float = 6.28

文字列の結合は^

# "hoge" ^ "fuga";;
- : string = "hogefuga"

#use "filename"でファイルを読み込む. 本文中テストはこの方法で実行している.

# #use "9_list.ml";;
val contain_zero : 'a -> bool = <fun>
val test1 : bool = true
val test2 : bool = false
val test3 : bool = true
val test4 : bool = false
val test5 : bool = false

2章: 変数の定義

let pi = 3.1415 ;;
(* val pi : float = 3.1415 *)
pi;;
(* - : float = 3.1415 *)

もう一度letすればふつうに書き換えできる.

let pi = 12345 ;;
(* val pi : int = 12345 *)
pi;;
(* - : int = 12345 *)

letなしの=は等価性比較. ==ではない.

pi = 123 ;;
(* - : bool = false *)
pi;;
(* - : int = 12345 *)

4章: 関数の定義

定義には変数と同じletを使う. let var = val だと変数で, let func arg... = exec だと関数かな?

let f x = 3 * x ;;
(* val f : int -> int = <fun> *)
f 4;;
(* - : int = 12 *)

ここで, 関数fには「返り値がintである」という型付けがなされている. OCamlは強く型付けされている.

ただし「関数の型」 != 「関数が返す結果の型」であることに注意.
int -> int というのが関数の型. 「intを受け取ってintを返す関数」である. int -> int で「関数の型」になる.

let g x y = x * x + y * y - 4 ;;
(* val g : int -> int -> int = <fun> *)
g 3 4 ;;
(* - : int = 21 *)

let bmi m kg = kg /. (m *. m) ;;
(* val bmi : float -> float -> float = <fun> *)
bmi 1.78 78.0 ;;
(* - : float = 24.6181037747759106 *)

5章: 条件分岐

if 2 > 0 then true else false ;;
(* - : bool = true *)

早速Fibonacci書こうと思ったけど

let fib n =
  if n <= 1 then 1
  else fib (n - 1) + fib (n - 2) ;;
(* Error: Unbound value fib *)

再起できない? => ポイントはlet recだった(10章). 再帰するときはこれが必要

let rec fib n =
    if n <= 1 then 1
    else fib (n - 1) + fib (n - 2) ;;

fib 0;; (* - : int = 1  *)
fib 2;; (* - : int = 2  *)
fib 9;; (* - : int = 55 *)
```

ok


6章: さまざまなエラー
========================

```ocaml
3 + _2.4_ ;;
(* Error: This expression has type float but an expression was expected of type int *)

OCamlインタプリタはエラーがある箇所に下線を引いてくれる

7章: 組とパターンマッチ

組. タプル, cons cell的なもの

(3.14, 2.71) ;;
(* - : float * float = (3.14, 2.71) *)
```

> 組の型は要素の型を`*`でつないだものになります

つまり全体として「`float * float`」型.

```ocaml
"a", true, (3.3, "b") ;;
(* - : string * bool * (float * string) = ("a", true, (3.3, "b")) *)

要素の型は自由. 要素は2個じゃなくてもいい. カッコは省略できる.

let add pair = match pair with
     (a, b) -> a + b ;;
(* val add : int * int -> int = <fun> *)

add (4, 5) ;;
(* - : int = 9 *)

int * intの組（つまり(3,4)とかそういうの）を渡すとintを返す関数addを定義してる.

同様に, 最初からpairを引数として受け取ることも出来る

let add2 (a,b) = a + b ;;
(* val add2 : int * int -> int = <fun> *)
add2 (4, 5) ;;
(* - : int = 9 *)

car, cdr的なことをするにはパターンマッチする必要ある? めんどくさいな

let car pair = match pair with
  (a, b) -> a ;;
(* val car : 'a * 'b -> 'a = <fun> *)

car pair ;;
(* - : int = 1 *)

上述の通り関数定義の引数にパターンを置けるので, こうも書ける

let car (a, b) = a ;;
(* val car : 'a * 'b -> 'a = <fun> *)

8章: レコード

本文, レコード定義方法書かずにいきなり使い方から入るから混乱した

{ name = "a" } ;;
(* Error: Unbound record field label name *)

正しくはtype文で定義した後に使う.

type study = {
  name : string;
  score : int;
  rank : string;
};;

(* type study = { name : string; score : int; rank : string; } *)
{ name="hash"; score=80; rank = "B" } ;;
(* - : study = {name = "hash"; score = 80; rank = "B"} *)

// Kobitoのシンタックスハイライトが{をコメントとみなす?

フィールドの組み合わせからtypeを見つけてくれるのか.
フィールド名は(他のレコードであっても)重複不可能. 名前空間で分離できないの?

9章: リスト

空リスト: []
リストに要素追加: :: -- 右結合.

OCamlのリスト結合(とパターンマッチでの分解)命令::なのか, Haskellみたいに:の方が見やすいのに.

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

こうも定義できる

[ 9; 8; 7 ];;
(* - : int list = [9; 8; 7] *)

さっきから出て来てるint listが型. なんちゃらリストになるぽい
ちなみに要素の型は統一されねばならない

[true; 1; "str"] ;;
(* Error: This expression has type int but an expression was expected of type 
         bool *)

要素へのアクセスも(組やレコードと同じく)パターンマッチ. えーそうなの. パターンマッチ勢力強いな

パターンマッチのパターンが足りないと(たとえばカラリストの場合を抜かすと) Warningが出る. 親切

再帰

再帰関数の定義はletではなくlet recで行う!!

let rec mapSquare list = match list with
    [] -> []
  | first :: rest -> (first * first) :: mapSquare rest;;
(* val mapSquare : int list -> int list = <fun> *)
mapSquare [1; 2; 3; 4; 5];;
(* - : int list = [1; 4; 9; 16; 25] *)

できた. recなしletだけで定義するとError: Unbound value mapSquareと怒られる.

let rec contain_zero lst = match lst with
    [] -> false
  | first :: rest -> if first = 0 then true
                     else contain_zero rest

let test1 = contain_zero [] = false
let test2 = contain_zero [0; 2] = true
let test3 = contain_zero [1; 2] = false
let test4 = contain_zero [1; 2; 0; 4; 5] = true
let test5 = contain_zero [1; 2; 3; 4; 5] = false

10章: 再帰関数を使ったプログラミング

let rec min lst = match lst with
    [] -> max_int
  | first :: rest -> if first <= (min rest) then first
                     else min rest

let testmin1 = min [] = max_int
let testmin2 = min [1; 2; 3] = 1
let testmin3 = min [3; 2; 1] = 1
let testmin4 = min [3; 1; 2] = 1

max_intはint = 4611686018427387903を表す定数. これでいいのかよ, と思うなら18章の例外処理を使いなさいとのこと

局所変数

Lispの(let (var val) (...)) にあたるものぽい

let z = 2;;
(* val z : int = 2 *)
z + z ;;
(* - : int = 4 *)
let x = 2 in x + x ;;
(* - : int = 4 *)
x + x ;;
(* Error: Unbound value x *)

これで結果を束縛すればminの呼び出しが一回で済む.

let rec min lst = match lst with
    [] -> max_int
  | first :: rest ->
     let min_rest = min rest in
     if first <= min_rest then first
     else min_rest

Haskellみたいにインデントは必須ではない?

11章: 自然数と再帰

階乗の作り方とかそういう話

let rec fac n =
  if n <= 1 then 1
  else n * fac (n - 1) ;;
(* val fac : int -> int = <fun> *)
fac 5 ;;
(* - : int = 120 *)
fac 10 ;;
(* - : int = 3628800 *)

12章: ダイクストラのアルゴリズム

重み付きグラフの最短経路を求めるアルゴリズム.

各線の数が重み

13章: 一般化と高階関数

関数を引数に取る関数. 例としてmapを作ってみる

let rec myMap func lst = match lst with
    [] -> []
  | first :: rest -> func first :: myMap func rest;;
(* val myMap : ('a -> 'b) -> 'a list -> 'b list = <fun> *)

'aは「型変数」. アルファ, と読むらしい. どんな型が入ってもよいという意味で「多相性(polymorphism)」と呼ばれる. 型変数を含む型は「多相型」.

プログラミング言語の型システムの性質を表すもので、プログラミング言語の各要素（定数、変数、式、オブジェクト、関数、メソッドなど）についてそれらが複数の型に属することを許すという性質を指す。
ポリモーフィズム - Wikipedia

OCamlの関数は第一級関数なので, 関数を返す関数も定義できる.

let twice f =
    let g x = f (f x)
    in g ;;
(* val twice : ('a -> 'a) -> 'a -> 'a = <fun> *)

twice (fun x -> x * 2);;
(* - : int -> int = <fun> *)

let hoge = twice (fun x -> x * 2);;
(* val hoge : int -> int = <fun> *)

hoge 2;;
(* - : int = 8 *)

twiceは関数(これはf (f x)の記述から'a -> 'a型の関数であると推論できる)を受け取り, その関数を2回適用させるような関数を返す.

14章: 高階関数を使ったリスト処理

filterとかreduce(fold)とかそのへんの話.

let rec filter judge lst = match lst with
    [] -> []
  | first :: rest ->
     if judge first then first :: filter judge rest
     else filter judge rest
(* val filter : ('a -> bool) -> 'a list -> 'a list = <fun> *)

filter (fun x -> x > 0) [-1; 2; 3; -4];;
(* - : int list = [2; 3] *)

sum up

let rec sum lst = match lst with
  [] -> 0
  | first :: rest ->
  first + sum rest;;
(* val sum : int list -> int = <fun> *)

sum [1; 2; 3; 4; 5];;
(* - : int = 15 *)

let rec foldr f lst init = match lst with
    [] -> init
  | first :: rest -> f first (foldr f rest init);;
(* val foldr : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun> *)

foldr (fun x y -> x + y) [1; 2; 3; 4; 5] 0;;
(* - : int = 15 *)

foldr(right)の様子

逆のfoldもあるね

let rec foldl f lst init = match lst with
    [] -> init
  | first :: rest -> foldl f rest (f init first);;
(* val foldl : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun> *)

foldl (fun x y -> x + y) [1; 2; 3; 4; 5] 0;;
(* - : int = 15 *)

foldl(left)の様子

局所関数

let hoge x =
  let fuga x = x * x
  in (fuga x) * (fuga x);;
(* val hoge : int -> int = <fun> *)

hoge 2;;
(* - : int = 16 *)

無名関数

今までも使ってきたがfun args... -> body.

その場実行

(fun x -> x * 100) 90;;
(* - : int = 9000 *)

無名なので再帰できない.

infix/prefix関数

基本的にprefix(前置記法)だが+などの演算子はinfix(中置記法). infixな演算子も()でくくってやるとprefixで使える

(+) 1 2;;
(* - : int = 3 *)

これを使えば上でやったように無名関数で足し算を表現しなくても+を引数として高階関数に渡せて便利

foldr (+) [1; 2; 3] 0;;
(* - : int = 6 *)

foldr + [1; 2; 3] 0;;
(* Error: This expression has type ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
      but an expression was expected of type int *)

つづき

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