『プログラミングの基礎』読書会
接頭語を返す関数 prefix を補助関数 add_to_each を使って作る
接頭語
-
[1;2;3]というリストの接頭語は[[1]; [1;2]; [1;2;3]] -
空リストは接頭語に含めない
各接頭語の先頭にもうひとつ要素を付け加える
(* テスト *)
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]]
let test4 = add_to_each 1 [[2]; [2;3]; [2;3;4]]
= [[1;2]; [1;2;3]; [1;2;3;4]](* 目的: 受け取った lst の要素それぞれの先頭に n をくっつける *)
(* add_to_each : int -> int list list -> int list list *)
let rec add_to_each n lst = match lst with
[] -> []
| first :: rest -> [] (* add_to_each n rest *)
リストの接頭語を求める
(* テスト *)
let test5 = prefix [] = []
let test6 = prefix [1]
= [[1]]
let test7 = prefix [1; 2]
= [[1]; [1;2]]
let test8 = prefix [1; 2; 3; 4]
= [[1];[1; 2];[1; 2; 3];[1; 2; 3; 4]](* 目的:受け取った lst の接頭語のリストを求める *)
(* prefix : int list -> int list list *)
let rec prefix lst = match lst with
[] -> []
| first :: rest -> [] (* prefix rest *)-
関数から別の関数を呼び出すことで、より複雑な関数を作ることができる
-
関数呼び出しの結果をほかの関数に渡すことができる（関数呼び出しをネストする）
(* テスト *)
let test1 = minimum [3] = 3
let test2 = minimum [1; 2] = 1
let test3 = minimum [3; 2] = 2
let test4 = minimum [3; 2; 6; 4; 1; 8] = 1
(* 目的: 受け取った lst の中の最小値を返す関数 *)
(* minimum : int list -> int *)
let rec minimum lst = match lst with
[] -> ()
| first :: rest -> 0 (* minimum rest *)-
空リストのときは max_integer（どの要素よりも大きいint）
-
first が rest の最小と同じかまたは小さいなら first を返す
(* minimum : int list -> int *)
let rec minimum lst = match lst with
[] -> max_int
| first :: rest ->
if first <= minimum rest
then first
else minimum restただし、この実装では次のような特殊な場合を区別できない
-
入力されたリストが空
-
要素が全部 max_int
テスト書いてみよう
これらを特殊な場合として扱うには 例外処理 （18章）を使います
(* minimum : int list -> int *)
let rec minimum lst = match lst with
[] -> max_int
| first :: rest ->
if first <= minimum rest
then first
else minimum restminimum rest かぶっとるやん (´・ω・｀)
そこで 局所変数
let 変数名 = 式1 in 式2
式1を値としてもつ、式2の中でのみ有効な 局所的な変数
変数の有効範囲のことを スコープ という
-
トップレベルの変数と同名の局所変数
-
入れ子の局所変数
(* minimum : int list -> int *)
let rec minimum lst = match lst with
[] -> max_int
| first :: rest ->
let min_rest = minimum rest in
if first <= min_rest
then first
else min_rest成績がAの人、Bの人、Cの人、Dの人がそれぞれ何人いるかを４つ組にして返す関数 shukei
type gakusei_t = {
namae : string;
tensuu : int;
seiseki : string;
}
(* 目的:学生リスト lst のうち各成績の人数を集計する *)
(* syukei : gakusei_t list -> int * int * int * int *)
let rec shukei lst = match lst with
[] -> (0, 0, 0, 0)
| {namae = n; tensuu = t; seiseki = s} :: rest ->
let shukei_rest = shukei rest in
match shukei_rest with
(a, b, c, d) ->
if s = "A" then (a + 1, b, c, d)
else if s = "B" then ( a, b + 1, c, d)
else if s = "C" then ( a, b, c + 1, d)
else ( a, b, c, d + 1)再帰呼び出し shukei rest の実行結果を shukei_rest にとっておいて、さらに match でパターンマッチ。いそがしい。
実は局所変数定義とパターンマッチを同時に行う方法がある。
let 変数名 = 式1 in 式2
は実は
let パターン = 式1 in 式2
(* 目的:学生リスト lst のうち各成績の人数を集計する *)
(* syukei : gakusei_t list -> int * int * int * int *)
let rec shukei lst = match lst with
[] -> (0, 0, 0, 0)
| {namae = n; tensuu = t; seiseki = s} :: rest ->
let (a, b, c, d) = shukei rest in
if s = "A" then (a + 1, b, c, d)
else if s = "B" then ( a, b + 1, c, d)
else if s = "C" then ( a, b, c + 1, d)
else ( a, b, c, d + 1)(* 目的: lst1 と lst2 を受け取りそれらを結合したリストを返す *)
(* append : 'a list -> 'a list -> 'a list *)
let rec append lst1 lst2 = match lst1 with
[] -> lst2
| first :: rest -> first :: append rest lst2
(* テスト *)
let test1 = append [] [] = []
let test2 = append [] [1; 2] = [1; 2]
let test3 = append [1; 2] [] = [1; 2]
let test4 = append [1; 2] [3; 4;] = [1; 2; 3; 4]
let test5 = ["a"; "b"; "c"; "d"; "e"] ["f"; "g"]
= ["a"; "b"; "c"; "d"; "e"; "f"; "g"]同じものが List.append としてOCamlに定義されている
@ というショートカットが演算子として用意されている
いずれにしろリストの結合は先にくるリストの長さに比例した実行時間がかかるので注意！
(* ふたつの昇順に並んだリストをマージする関数 *)
(* merge : int list -> int list -> int list *)
let rec merge lst1 lst2 = match (lst1, lst2) with
([], []) -> []
| ([], first2 :: rest2) -> lst2
| (first1 :: rest1, []) -> lst1
| (first1 :: rest1, first2 :: rest2) ->
if first1 < first2
then first1 :: merge rest1 lst2
else first2 :: merge lst1 rest2
(* テスト *)
let test1 = merge [] [] = []
let test2 = merge [] [1; 2] = [1; 2]
let test3 = merge [1; 2] [] = [1; 2]
let test4 = merge [1; 3] [2; 4] = [1; 2; 3; 4]
let test5 = merge [2; 4] [1; 3] = [1; 2; 3; 4]
let test6 = merge [1; 4] [1; 3] = [1; 1; 3; 4]ふたつのリストをうけとってきたら、それらの長さが同じかどうかを判定する関数 equals_length をデザインレシピにしたがって作れ。（length は使わずに作成せよ。)