プログラミングの基礎 /浅井健一 9~10 メモ

プログラミングの基礎 / 浅井健一　メモ

• プログラミングの基礎の学習メモです
• この本は8章「レコード」までは OCaml の基本文法を紹介しています
• 9章「リスト」から再帰関数が登場し、内容が抽象的になっていきます。このメモは9章から17章までをまとめたものになります

デザインレシピ

（かなり）簡略化すると以下のようになる。

1. 具体例を作成する
2. 入出力の型を定義する。プログラムの目的を言語化する
3. プログラムを作成しテストする

第9章 リスト

リストの定義

• そもそもリストは自分自身を使って定義（再帰的定義）される
• このようなデータ型を『再帰的なデータ型』と呼ぶ

定義1 空リスト[]はリストである。
定義2 first が要素, rest がリストなら first :: rest もリストである。

• 定義1によって、空のリストだけは無条件に作成できる
• 定義2は自己参照している。（定義すべきリスト自体を rest として使用している）
• 定義全体から任意の要素数のリストを作成することができる
• 一行目の定義から無条件で空のリストが作成でき、二行目の定義から任意の要素数のリストが作成できる

再帰関数

• 再帰関数は関数型プログラミングの強力なループ処理である

再帰関数の基本的な形

• リストの定義から、リストは再帰的な構造を持っていることが分かる
• このようなデータ型では、その構造にしたがって再帰関数をつくることができる

(* 'a list -> ? *)
(* saiki: リストが与えられたらパターンマッチをする。[]の場合はなんらかの値を返し、そうでない場合は残りのリストに対して再帰的に saiki を実行する *)
let rec saiki lst = match lst with
  [] -> (* 答えが自明なケース *)
  | first :: rest -> saiki rest (* 答えが自明ではないケース *)

• リストのパターンマッチの結果が、再帰的なデータ型であるリストの定義の 1 と 2 に対応している。
  • []の場合は答えが自明である。（定義1に対応）
  • first :: rest の場合は自己参照 saiki rest が起こる。（定義2に対応）

length

基本的な再帰関数

(* int list -> int *)
(* length: 整数の入ったリストを与えられたら、その長さ(要素数)を返す *)
let rec length lst = match lst with
  [] -> 0
  | firest :: rest -> length rest + 1

let test1 = length [] = 0
let test2 = length [1] = 1
let test3 = length [1; 2; 3] = 3
let test3 = length [1; 2; 3; 4; 5] = 5

この関数 length の目的は『リストの長さを返すこと』である。

答えが自明なケースはリストが空の場合で、このときリストの長さは 0 なので 0 を返す。
答えが自明でないケースではループ処理をするために再帰的に length を実行する。ただし、このとき length に list を渡すと無限ループに陥るので要素がひとつ減った rest を渡す。

length rest の出力を日本語にして考えてみる。
length の目的は『リストの長さを返すこと』である。
したがって length rest は 『rest の長さ』を出力する。

具体的にリスト[1; 2; 3]の場合で考えてみると、このリストは
　first: 1
rest: [2; 3]
という具合にパターンマッチされ length rest は length [2; 3] となって 2 を出力する。

test3を参照すると length [1; 2; 3]は 3 を出力している。
この場合 length rest = 2 に +1 したものが答えとなる。

以上から、答えが自明でないケースは length rest + 1 となる。
この式は他のテストでも同様に目的を達成する。

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

• いろいろな再帰関数が紹介されている
  • ネストした再帰関数 : prefix, ins_sort
  • 局所変数定義を使った再帰関数 minimum
  • 2つ以上のパターンにマッチする merge関数

関数のネスト（関数の中で関数を呼ぶ）

ins_sort (インサートソート or 挿入ソート)

• 昇順リストに整数を挿入する insert を使って、整列アルゴリズムの挿入ソート ins_sort を作成する。
• 関数の中でべつの関数を呼んでいる。

insert

(* int list -> int -> int list *)
(* insert : 昇順リストと整数を与えられたら昇順になるように整数を挿入する *)

let rec insert lst n = match lst with
  [] -> [n]
  | first :: rest -> if n < first then n :: lst
                                  else first :: insert rest n

let test2 = insert [1; 3; 4; 7; 8] 5 = [1; 3; 4; 5; 7; 8]

ins_sort

(* ins_sort : 整数のリストを与えられたら、昇順にして返す *)
(* int list -> int list *)
let rec ins_sort lst = match lst with
  [] -> []
  | first :: rest -> insert (ins_sort rest) first

let test2 = ins_sort [5; 3; 8; 1; 7; 4] = [1; 3; 4; 5; 7; 8]

gakusei_sort

• レコードの入ったリストを扱う。

let rec gakusei_insert lst gakusei = match lst with
  [] -> [gakusei]
  | ({namae = n; tensuu = t; seiseki = s} as first) :: rest -> 
  match gakusei with
    {namae = n2; tensuu = t2; seiseki = s2} ->
      if t2 < t then gakusei :: lst
                else first :: gakusei_insert rest gakusei

• リストの中のレコードでパターンマッチする。
  • まずはじめにリストをパターンマッチさせ、次にレコードデータをパターンマッチし、処理を書く

(* gakusei list -> gakusei list *)
(* gakusei_sort : gakusei_t リストが与えられたら、点数の昇順に整列して返す *)

let rec gakusei_sort lst = match lst with
  [] -> []
  | ({namae = n; tensuu = t; seiseki = s} as first) :: rest ->
    gakusei_insert (gakusei_sort rest) first

局所変数定義（ローカル変数）

• minimum rest の結果を複数回使うときはローカル変数 min_rest としておくと計算し直さなくてよい

(* 目的 : 受け取った lst の中の最小値を返す *)
(* 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

パターンマッチの省略

• ローカル変数でもパターンマッチを省略して書くことができる

let shukei_rest = ketsueki_shukei rest in 
    match shukei_rest with (a, b, c, d) ->

let (a, b, c, d) = ketsueki_shukei rest in

マージ関数

• 与えられたふたつのリストを組にして場合わけしているところがポイント

(* int list -> int list -> int list *)
(* merge: 2つの昇順に並んだリストを与えられたら、1つにまとめる *)
let rec merge lst1 lst2 = match (lst1, lst2) with
  ([], []) -> []
  | ([], first2 :: rest2) -> first2 :: rest2
  | (first1 :: rest1, []) -> first1 :: rest1
  | (first1 :: rest1, first2 :: rest2) -> 
    if first1 < first2 then first1 :: first2 :: merge rest1 rest2
                       else first2 :: first1 :: merge rest1 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 [] [3; 4] = [3; 4]
let test4 = merge [1] [2] = [1; 2]
let test5 = merge [1; 2; 3] [2; 3; 4] = [1; 2; 2; 3; 3; 4]
let test6 = merge [1; 3; 5] [2; 4; 6] = [1; 2; 3; 4; 5; 6]