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

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

16章 情報の蓄積

• 再帰関数はループの過程を省略して記述できるが、過程の情報が欠落してしまう
• ループ中の情報を蓄積するための引数を用意する。この引数をアキュムレータと呼ぶ

アキュムレータ

total_distance

• ループ途中における合計距離を保存しておいて、計算に利用する

(* total_distance: distance_t型のリストを与えると、各点の合計距離を計算して返す *)
(* distance_t list -> distance_t list *)
let rec total_distance lst =
  (* hojo: 先頭からリスト中の各点までの距離の合計を計算する *)
  (* total0 はこれまでの距離の合計 *)
  (* distance_t list -> float -> distance_t list *)
  let rec hojo lst total0 = match lst with
    [] -> []
    | {kyori=k; total=t} :: rest -> {kyori=k; total= total0 +. k} :: hojo rest (k +. total0) in
  hojo lst 0.0

reverse

• 補助関数にアキュムレータを持たせる
• それまでの結果（逆順リスト）を result として保存して、すべて見終わったら返す

(* int list -> int list *)
(* reverse: 与えられたリストを逆順にして返す *)
let reverse lst =
  (* (lst の逆順のリスト) @ result を返す *)
  (* ここで result はこれまでの要素を逆順にしたリストを示す *)
  let rec rev lst result = match lst with
    [] -> result
    | first :: rest -> rev rest (first :: result)
  in rev lst []

let test1 = reverse [1; 2; 3] = [3; 2; 1]

• 引数2つの関数としても書ける

(* これでも可能 *)
let rec reverse2 lst result = match lst with
  [] -> result
  | first :: rest -> reverse2 rest (first :: result)

let test2 = reverse2 [1; 2; 3] [] = [3; 2; 1]
let test3 = reverse2 [1; 2; 3; 4; 5] [] = [5; 4; 3; 2; 1]

• fold_leftを使って書く。（左から順に追加していったら反転している）

let reverse3 lst =
  List.fold_left (fun ls a -> a :: ls) [] lst 

fold_left

• fold_right とは違って init の値が関数によって変化していく

(* 目的：init から始めて lst の要素を左から順に f を施し込む *) 
(* ('a -> 'b -> 'a) -> 'a -> 'b list *)
let rec fold_left f init lst = match lst with 
    [] -> init 
  | first :: rest -> fold_left f (f init first) rest 

fold_right と fold_leftの違い

• 基本的には「関数の適用が右からか、左からか」が違う
  • 実装的には以下のような違いがある。
    • 右：　fun first (fold_right rest)　：　先頭の要素と再帰関数の結果を計算する
    • 左：　fold_left (fun init first)　：　関数が適用された init を再帰的に実行する

List.fold_right (+) [1; 2; 3; 4; 5] 0 = 1 + (2 + (3 + (4 + (5 + 0))))

List.fold_left (+) 0 [1; 2; 3; 4; 5] = (((((0 + 1) + 2) + 3) + 4) + 5)

(* right と left の function が受け取る引数の違い *)
  (* fold_right: fun first (fold_right rest)*)
  (* fold_left: fold_left (fun init first) *)

(* fold_right (+) [1; 2; 3; 4 5] 0 *)
(* f 1 + (fold_right (+) [2; 3; 4; 5] 0) *)
(* f 1 + (f 2 + fold_right (+) [3; 4; 5] 0) *)
(* f 1 + (f 2 + (f 3 + (fold_right (+) [4; 5]) 0) *)
(* f 1 + (f 2 + (f 3 + (f 4 + (fold_right (+) [5]) 0))) *)
(* f 1 + (f 2 + (f 3 + (f 4 + (f 5 + fold_right (+) []) 0))) *)
(* f 1 + (f 2 + (f 3 + (f 4 + (f 5 + ( 0 ))))) *)
(* f 1 + (f 2 + (f 3 + (f 4 + (5))))) *)
(* f 1 + (f 2 + (f 3 + (9))) *)
(* f 1 + (f 2 + (12)) *)
(* f 1 + 14 *)
(* 15 *)

(* fold_left 0 [1; 2; 3; 4; 5] *)
(* fold_left (f 0 1) [2; 3; 4; 5] *)
(* fold_left (f 1 2) [3; 4; 5] *)
(* fold_left (f 3 3) [4; 5] *)
(* fold_left (f 6 4) [5] *)
(* fold_left (f 10 5) [] *)
(* fold_left f (15) [] *)
(* fold_left 15 *)

17章 再帰的なデータ構造

• 再帰的なデータ構造である木を扱う
  • 二分木と二分探索木
• 要素が存在しないかもしれないという場合を表現するためにバリアント型を用いる

バリアント型

• バリアント(variant="多様な")型

nengou

• 元号と引数として年数を受け取る。年号。

type nengou_t = 
  Meiji of int
  | Taisho of int
  | Showa of int
  | Heisei of int
  | Reiwa of int

• バリアント型と引数の値に応じて計算する

(* to_seireki：年号を受け取ったら対応する西暦年を返す *)
(* nengou_t -> int*)
let to_seireki nengou = match nengou with
  Meiji (n) -> n + 1867
  | Taisho (n) -> n + 1911
  | Showa (n) -> n + 1925
  | Heisei (n) -> n + 1988
  | Reiwa (n) -> n + 2018

let test1 = to_seireki (Meiji (1)) = 1868
let test2 = to_seireki (Reiwa (10)) = 2028

二分木(binary tree)

tree_t

• 木構造をバリアント型で表現する

(*
  tree は
  - Empty                 空の木、あるいは
  - Leaf (n)              値が n の葉、あるいは
  - Node (t1, n, t2)      左の木が t1、値が n, 右の値が t2 であるような節
                          (t1 と t2が自己参照のケース)
*)

(* 二分木を表す型 *)
(* type 'a で多相形の宣言 *)
type 'a tree_t = 
    Empty (* 空の木 *)
  | Leaf of 'a (* 葉 *)
  | Node of 'a tree_t * 'a * 'a tree_t (* 節 *)

sum_tree

• tree に含まれる整数の合計を返す
• 木は再帰構造なので、構造に従って再帰関数が書ける
  • 自明なケース：Empty Leaf
  • ループが起こるのは Node
    • Node ではそれ以下の二つの木に対してループする

(* sum_tree: tree に含まれる整数をすべて加える *)
(* sum_tree: tree_t -> int *)
let rec sum_tree tree = match tree with
  Empty -> 0
  | Leaf (n) -> n
  | Node (t1, n, t2) -> sum_tree t1 + n + sum_tree t2

tree_map

• 木のすべての要素に与えた関数を適用する
• sum_treeと同様に、構造に従って書ける

(* int -> int 型の関数 f と tree_t 型の木を受け取ったら、節や葉に入っている値すべてに f を適用した木を返す関数 tree_map *)
(* (int -> int) -> tree_t -> tree_t *)
let rec tree_map f tree = match tree with
  Empty -> Empty
  | Leaf (n) -> Leaf (f n)
  | Node (t1, n, t2) -> Node (tree_map f t1, f n, tree_map f t2)

let add1 x = x + 1
tree_map add1 tree

tree_depth

• 木の深さを返す = ルートの左右の木の深いほうの「深さ」を返す
  • 「深さ」は Node を通るたびに +1 していった値

(* tree_depth: tree_t型の木を受け取ったら木の深さを返す。
               木の深さ：　根から葉、または空の木に至る最長の道に含まれる節の数 *)
(* tree_t -> int *)

let rec tree_depth tree = match tree with
  Empty -> 0
  | Leaf (n) -> 0
  | Node (t1, n, t2) ->
    let d1 = tree_depth t1 + 1 in (* 左の木の深さ *)
    let d2 = tree_depth t2 + 1 in (* 右の木の深さ *)
      if d1 > d2 then d1 else d2

二分探索木(binary search tree)

条件

• 節の左の木の値は、どれもその節の値よりも小さい
• 節の右の木の値は、どれもその節の値よりも小さい

(* 二分探索木：　binary search tree *)
let tree1 = Empty
let tree2 = Leaf (3)
let tree3 = Node (Leaf (1), 2, Leaf (3))
let tree4 = Node (Empty, 7, Leaf (9))
let tree5 = Node (tree3, 6, tree4)

search

• 二分探索木に data が含まれているか判定する
  • 節の場合 data と節の値の大小によって探索する木を選択する
  • 二分探索木だから可能

(* search: data が2分探索木 tree に含まれているかを調べる *)
(* 'a tree_t -> 'a -> bool *)
let rec search tree data = match tree with
  Empty -> false
  | Leaf (n) -> data = n
  | Node (t1, n, t2) ->
    if n = data then true
                else if data < n then search t1 data
                else search t2 data

insert_tree

• 二分探索木の性質に従って条件分岐する。
  • 葉の場合、適当な Empty に与えたデータを追加する
  • 節の場合、適当な Node でループする

(* insert_tree: 2分探索木 tree に data を追加した2分探索木を返す *)
(* 'a tree_t -> 'a -> 'a tree_t *)
let rec insert_tree tree data = match tree with
  Empty -> Leaf (data)
  | Leaf (n) ->
    if n = data then Leaf (n)
    else if data < n then Node (Leaf (data), n, Empty)
                     else Node (Empty, n, Leaf(data))
  | Node (t1, n, t2) -> 
    if data = n then Node (t1, n, t2)
    else if data < n then Node (insert_tree t1 data, n, t2)
                     else Node (t1, n, insert_tree t2 data)