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


環境構築
==============================

### Ubuntu

```console
$ sudo apt-get install ocaml-nox
```

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

### Emacs

ocaml-modeは微妙という評価を見かけたので[tuareg-mode](http://www.emacswiki.org/emacs/TuaregMode)を使う. いまのところ問題なく使えている
`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;;
```

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

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

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

文字列の結合は`^`

```haskell
# "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章: 変数の定義
=====================

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

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

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

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

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


4章: 関数の定義
====================


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

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

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

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

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

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

5章: 条件分岐
========================

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

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

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

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

````ocaml
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的なもの

````ocaml
(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個じゃなくてもいい. カッコは省略できる.

```ocaml
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を引数として受け取ることも出来る

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

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

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

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

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

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


8章: レコード
=============================

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

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

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

```ocaml
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みたいに:の方が見やすいのに.

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

こうも定義できる

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

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

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

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

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


## 再帰

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

````ocaml
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`と怒られる.

````ocaml
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章: 再帰関数を使ったプログラミング
====================================


````ocaml
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) (...))` にあたるものぽい

````ocaml
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の呼び出しが一回で済む.

````ocaml
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章: 自然数と再帰
==========

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

```ocaml
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章: ダイクストラのアルゴリズム
============================

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

![2014-07-01 at 11.06 AM.png](https://qiita-image-store.s3.amazonaws.com/0/682/3c590284-48cc-eafe-16a8-a1f965da0681.png "2014-07-01 at 11.06 AM.png")

各線の数が重み


13章: 一般化と高階関数
===============================

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

```ocaml
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](http://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%AA%E3%83%A2%E3%83%BC%E3%83%95%E3%82%A3%E3%82%BA%E3%83%A0)

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

```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)とかそのへんの話.

```ocaml
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

```ocaml
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 *)
```


```ocaml
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)の様子

![2014-07-08 at 6.45 PM.png](https://qiita-image-store.s3.amazonaws.com/0/682/7277b90c-fd32-982d-b24b-7568945c0bb7.png "2014-07-08 at 6.45 PM.png")


逆のfoldもあるね

```ocaml
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)の様子

![2014-07-08 at 6.56 PM.png](https://qiita-image-store.s3.amazonaws.com/0/682/a04fed16-b987-4fc8-3127-1b26f5bd1ec5.png "2014-07-08 at 6.56 PM.png")


### 局所関数

```ocaml
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`.

その場実行

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

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

### infix/prefix関数

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

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

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

```ocaml
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](http://qiita.com/hash/items/e78ef70dc2782e64c873)