「プログラミングの基礎」を読んだ。
読んだ理由
関数型言語を触ってみたかった。
環境構築
M1Macを使っている。以下コマンドで構築できる。
brew install ocaml
昔はDockerとか使って環境作ってたけどわざわざディレクトリ移動してコンテナ起こしたり、終わったら消したりなどが面倒になってしまって、結局自分のローカルに落とすのが楽という結論にいたった。本を読み終わったらしばらく使わないので uninstall する予定です。
8章 レコード
8章からメモ書き始めたので、ここから書いてます。
Ocamlのレコード（連想配列。JavaScriptでいうオブジェクトのようなもの）は、先にtype指定しないとエラーが出る。
# { test = "Can I create a record?"};; # Error: Unbound record field test
先にtypeを宣言しておくと、エラーが消える。
# type test = { test: string };; type test = { test : string; } # { test = "Can I create a record?"};; - : test = {test = "Can I create a record?"}
9章 リスト
Ocamlでのリスト処理。（配列処理)
# 2 :: 1 :: [];; - : int list = [2; 1] # [1; 2; 3;];; - : int list = [1; 2; 3]
中身の処理はパターンマッチを使う。
# match [] with [] -> 0 | first :: rest -> first;; - : int = 0
上の例の場合、firstにはリストの0番目、restにはリストの0番目を抜いたリストが格納されている。
Ocamlにおける、リストに0が含まれてるか確認する関数は以下のように再帰的に関数を作ることで定義できる。（定義時、 recursionの略語であるrecを書く必要がある。）
let rec filter list = match list with [] -> false | first :: rest -> if first 0 then true else filter rest;;
渡されたリストのint[]を全て合計した値を返す関数は以下。
let rec sum list = match list with [] -> 0 | first :: rest -> first + sum rest;;
Ocamlのような関数型言語では、ループは再帰を使って実装するケースが非常に多い。
10章 再起関数を使ったプログラミング
リストの中のリストの先頭に数字を追加する関数の書き方は以下。
let rec add_to_each num list = match list with [] -> [] | first :: rest -> ( num :: first ) :: add_to_each num rest;; let test1 = add_to_each 1 [] = [] let test2 = add_to_each 1 [[2]] = [[1; 2;]] let test3 = add_to_each 1 [[2]; [2; 3]] = [[1; 2;]; [1; 2; 3]]
局所変数を使えば、定義した変数を in の後に続く式の中でのみ有効なものとして扱える。
# let x = 2 in x + x;; - : int = 4
以下のように扱う。
let rec minimum list = match list with [] -> max_int | first :: rest -> let min_rest = minimum rest if first <= min_rest then first else min_rest
10.4について、p.100 に「たとえ一度しか使わなかったとしても rest の集計結果に名前をつけておくことは無駄ではありません。」とあるけれど、どう無駄でないのかよくわからないな…と思ったら、次ページで以下のようにパターンマッチで取り出していた。
let (a, b, c, d) = syukei rest
まだなんともいえないけど、これはつまり、「このパターンマッチでの取り出し」の伏線のためにp.100の記述があったわけで、p.100時点では「一度しか使わない集計結果に名前をつけるのは無駄」ではないだろうか、と思った。
「無駄ではない」という記述で、局所関数のスコープが再帰的に呼び出した関数の中でも適応内なのかな、と思ってしまいましたが、そういうわけではなさそうです。
11章 自然数と再帰
(* 階乗を求める関数 *) let rec fac n = if n = 0 then 1 else n * fac (n - 1) (* べき乗を求める関数 *) let rec power m n = if n = 0 then 1 else m * power m (n - 1)
13章 一般化と高階関数
(* 実数のリストlstを毛とり、各要素の平方根のリストを返す *) let rec map_sqrt list = match list with [] -> [] | first :: rest -> sqrt first :: map_sqrt rest
13.4 値として関数
以下の関数 twice7 について「引数として関数を受け取り、その関数を7に対して二回適用するような関数」と記述されていたが、たぶん正確には「引数として関数を受け取り、最初にその関数の引数を7として実行させ、次にその関数の戻り値を引数として再びその関数を実行する」かな、と思った。前者の書き方だと、1回目の関数実行結果を2回目が利用していないことになる。
let twice7 f = f (f 7);; let add3 x = x + 3;; twice7 add3;; - : int = 13
14章 高階関数を使ったリスト処理
この章はかなり勉強になりました。
(* 受け取ったリストlstから正の要素のみを取り出す *) let rec filter_positive lst = match lst with [] -> [] | first :: rest -> if first > 0 then first :: filter_positive rest else filter_positive rest;;
(* init から始めて、lstの要素を右から順に f を施し込む *) let rec right_fold f lst init = match lst with [] -> init | first :: rest -> f first (right_fold f rest init);;
(* 局所関数定義を利用しながら、受け取ったリストlstの各要素の和を求める *) let sum lst = let add_int first rest = first + rest in right_fold add_int lst 0;;
無名関数の作り方は以下.
# (fun x -> x + 1) 5;; - : int = 6
無名関数を使ってsumを作る
let sum lst = right_fold (fun first result -> first + result) lst 0;;
infix関数をprefix関数として渡す方法は以下。
let sum lst = right_fold (+) lst 0;;
15章 新しい形の再帰
クイックソートの実装。（本書と書き方が違うけど、かなり簡潔にかけた気がした。）
let rec quick_sort lst = match lst with [] -> [] | first :: rest -> quick_sort (List.filter (fun item -> item < first) rest) @ [first] @ quick_sort (List.filter (fun item -> item > first) rest);;
16章 情報の蓄積
let total_distance lst = let rec hoko lst total0 = match lst with [] -> [] | { kyori = k, total = t} :: rest -> { kyori = k, total = k +. total0} :: hojo rest (total0 + .k) in hojo lst 0.0
