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

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

11章 自然数と再帰

自然数の構造

定義1 ０は自然数である。
定義2 n が自然数なら n + 1 も自然数である。

リスト同様、再帰的定義。構造に従った再帰関数を作ることができる。

階乗

(* int -> int *)
(* fac: 自然数nが与えられると、nの階乗を返す *)

let rec fac n = 
  if n = 0 then 1
  else n * fac (n - 1)

let test1 = fac 0 = 1
let test2 = fac 1 = 1
let test3 = fac 2 = 2
let test4 = fac 3 = 6
let test5 = fac 4 = 24
let test6 = fac 5 = 120

冪乗

(* int -> int -> int *)
(* power: 自然数 n と m が与えられたら n の m 乗を返す *)
let rec power n m =
  if m = 0 then 1
  else n * power n (m - 1)

let test1 = power 2 0 = 1
let test2 = power 2 1 = 2
let test3 = power 2 2 = 4
let test4 = power 2 3 = 8

13章 一般化と高階関数

一般化の基本

• 似たような形があったとき、違った箇所を引数に取ることで一般化できる

データの一般化

(* 目的 : 個人情報リストを受け取ったら ketsueki0 の人数を返す *)
(* count_ketsueki : person_t list -> string -> int *)
let rec count_ketsueki lst ketsueki0 = match lst with
    [] -> 0
  | {namae = a; shintyo = s; taiju = t; birthday = birth; bloodType = blood} :: rest
  -> if blood = ketsueki0 then 1 + count_ketsueki rest ketsueki0
                          else count_ketsueki rest ketsueki0

関数の一般化

map

• 「リストの要素に対してなんらかの処理をする」関数の一般化 = map
  • リストの要素したい処理(関数)とリストを与えたら、処理した結果のリストを返す

(* ('a -> 'b) -> 'a lst -> 'b list *)
(* map: 関数とリストを与えたら、リストの要素に関数を実行した値を返す *)
let rec map f lst = match lst with
  [] -> []
  | first :: rest -> f first :: map f rest

let test1 = map sin [2.0; 4.0] = [0.909297426825681709; -0.756802495307928202]

• 関数型言語においては関数は普通の値（ファーストクラス）
• 関数を受け取る関数は高階関数と呼ぶ
• 多相型と多相関数（ポリモーフィズム/多相性）は、実行時に型が決定する

関数を返す関数

twice

(* twice: 関数を受け取ったらその関数を二回実行する関数を返す *)
let twice f =
  let g x = f (f x)
  in g

(* 具体例： 2乗を二回実行するから、2の2乗で4乗する関数を返す *)
let exponent n = n * n
let test1 = exponent 2 = 4
let test2 = (twice exponent) 3 = 81

fourtimes

(* 具体例: 2乗を4回実行するから、2の4乗で16乗する関数を返す *)
let fourtimes = twice twice
let test3 = (fourtimes exponent) 2 = 65536

compose

(* ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b *)
(* compose: 関数をふたつ与えられたら合成する *)
let compose f f2 =
  let g x = f (f2 x)
  in g

(* 具体例: 10倍と100倍を合成した「1000倍関数」を返す *)
let times10 n = n * 10
let times100 n = n * 100
let test1 = (compose times10 times100) 1 = 1000

• 関数も値のように2倍にしたり合成したり好きなように変化させられる