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

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

14章 高階関数を使ったリスト処理

• リストには似たような性質の大量のデータが入る
• リストの各要素に対して一括して処理をすることは、リストの本質的な操作
• 高階関数は関数に関数を渡す

条件を満たす要素を取り出す関数

filter

• 判定式とリストを与えたら、判定式に従ってリストをフィルタリングする

(* filter: 正の要素のみを取り出す *)
(* ('a -> bool) -> 'b list -> 'b list *)

let rec filter p lst = match lst with
  [] -> []
  | first :: rest -> 
    if p first then first :: filter p rest
               else filter p rest

filter_positive

(* 一般的な関数 filterから、具体的な関数 filter_positive を作成する *)
let positive n = 0 < n
let filter_positive lst = filter positive lst

let test1 = filter positive [-2; -1; 0; 1; 2] = [1; 2]

各要素をまとめあげる関数

fold_right

(* 空リストだったら何かひとつ値を返す、そうでなければ再起呼び出しをして、先頭の要素を使ってその結果になんらかの処理をする ような関数*)

let rec fold_right f lst init = match lst with
  [] -> init
  | first :: rest -> f first (fold_right f rest init)

sum,length,append (fold_rightで)

• fold_rightを使って作成した一般的な関数

(* fold_right を使って作成した具体的な関数 *)
let sum lst = fold_right (fun first rest -> first + rest) lst 0

let length lst = fold_right (fun first rest -> 1 + rest) lst 0

let append lst1 lst2 = fold_right (fun first rest -> first :: rest) lst1 lst2

infix 関数と prefix 関数

• prefix関数を使うとさらに短く書ける
  • infix: 3 + 5
  • prefix: + 3 5

let sum lst  = fold_right (+) lst 0
let concat lst = fold_right (^) lst ""

完全数を求める関数

perfect

• リスト全体を一括してひとつの値として扱うことは、抽象度の高い操作に繋がる
• リスト全体に一括処理を実行する map , fold_right, filter などの使用は、プログラムの簡潔さに繋がる。

(* perfect: m 以下の完全数のリストを返す *)
(* int -> int list *)
let perfect m = filter (fun n -> fold_right (+) (divisor n) 0 - n = n) (enumerate m)

let test1 = perfect 6 = [6]
let test2 = perfect 10000 = [8128; 496; 28; 6]

15章 新しい形の再帰

• 再帰的な構造に従わないより一般的な再帰

再帰関数の構造

• 一般的な再帰のポイント
  • 自明に答えが出るのはどんなケースか？
  • より小さな部分問題はどのようにしたら作れるか？
  • 再起呼び出しの結果から全体の結果を得るには？

部分問題の生成

quick_sort

• より小さな部分問題
  • take_smaller, take_bigger, take_equal
• 部分問題を quick_sort で解決する

(* quick_sort: 整数のリストが与えられたら、昇順にして返す *)
(* int list -> int list *)
let rec quick_sort lst =
  let take n lst p = List.filter (fun item -> p item n) lst in
    let take_smaller n lst = take n lst (<) in
    let take_bigger n lst = take n lst (>) in
    let take_equal n lst = take n lst (=) in
  match lst with
    [] -> []
    | first :: rest -> quick_sort (take_smaller first rest) @ take_equal first lst @ quick_sort (take_bigger first rest)

let test1 = quick_sort [] = []
let test2 = quick_sort [5; 4; 9; 8; 2; 3] = [2; 3; 4; 5; 8; 9]
let test3 = quick_sort [5; 4; 5; 5; 9; 8; 2; 3] = [2; 3; 4; 5; 5; 5; 8; 9]

停止性

一般に任意のプログラムが停止するかどうかを判定するアルゴリズムは存在しないことが知られている。決定不能。

停止性確認の方法

・ 再帰呼び出しを行う際の部分問題が、なんらかの意味でもとの問題よりも簡単になっていること。
・ それを繰り返すと、有限回で自明なケースに帰着されること。

一般の再帰に対するデザインレシピ

テンプレート

一般の再帰を使う場合には、自明に答えが出るケースとそれ以外のケースに場合わけする。典型的には以下のような if 文を使う。

if (* 自明に答えが出るケースの条件 *)
then (* 自明に答えが出るケース *)
else (* それ以外のケース *)

gcd

• 自明：　n = 0 then m
• 自明でない： gcd n (m mod n)
  • もとより小さな部分問題になっている。有限回数で解ける。

(* int -> int -> int *)
(* gcd: m と n の最大公約数を求める *)
(*  m >= n >= 0  *)
let rec gcd m n =
  if n = 0 then m
           else gcd n (m mod n)

let test1 = gcd 0 0 = 0
let test2 = gcd 2 0 = 2
let test3 = gcd 12 4 = 4
let test4 = gcd 12 5 = 1
let test5 = gcd 1071 1029 = 21

sieve

• 自明：　[] -> []

(* 素数: 1とそれ自身以外で割り切れない2以上の数 *)
(* sieve: 2以上n以下の自然数のリストを受け取ったら、素数だけ抽出して返す *)
(* int list -> int list *)
let rec sieve lst = match lst with
  [] -> []
  | first :: rest -> first :: sieve (List.filter (fun item -> item mod first != 0) rest)

let test1 = sieve [] = []
let test2 = sieve [2] = [2]
let test3 = sieve [2; 3; 4; 5; 6; 7; 8; 9; 10; 11] = [2; 3; 5; 7; 11]

prime

(* int -> int list *)
(* prime: 自然数nを与えると、n以下の素数を返す *)
let rec prime n = 
  let lst = List.filter (fun x -> n mod x = 0 && x != 1) (enumerate n) in
  if n = 0 || n = 1 then []  (* 自明なケース *)
    else if n = 2 then [2] (* 自明なケース *)
      else if List.length lst = 1 then lst @ prime(n - 1) (* 自明でないケースの条件 *)
      else prime(n - 1)　(* 自明でないケース *)

let test1 = prime 0 = []
let test2 = prime 1 = []

let test3 = prime 2 = [2]
let test4 = prime 13 = [13; 11; 7; 5; 3; 2]