2021-06-03 Thu. — 再帰とか高階関数とか。

勉強

プログラミング in OCaml (–Chapter 4)

練習問題 3.7

# let cond (b, e1, e2) : int =
    if b then e1 else e2;;

val cond : bool * int * int -> int = <fun>

# let rec fact n =
    cond ((n = 1), 1, n * fact (n - 1));;

val fact : int -> int = <fun>

# fact 4;;
Stack overflow during evaluation (looping recursion?).

なぜか。

OCamlは値呼び。fact 2からどうやって処理されるか見てみよう。

fact 2 --> cond ((2 = 1), 1, 2 * fact 1)
--> cond(false, 1, 2 * fact 1)
--> cond(false, 1, 2 * cond ((1 = 1), 1, 1 * fact 0))
--> cond(false, 1, 2 * cond (true, 1, 1 * fact 0))
--> cond(false, 1, 2 * cond (true, 1, 1 * cond((0 = 1), 1, fact (-1)))
--> cond(false, 1, 2 * cond (true, 1, 1 * cond(false, 1, (-1) * fact (-2))))
--> ...

値呼びなので引数に再帰があったらその再帰をすべて計算しないと終わらないが、この場合fact 1で止まらず、fact (-1), fact (-2), fact (-3)...と無限に再帰呼び出しが続く。

末尾再帰的fib

let rec iterfib (n, i, j) =
  if n = 1 then i
  else iterfib (n - 1, i + j, i);;

else以下にだけ再帰が現れる。 trace すると、

iterfib(4, 1, 1)
--> if 4 = 1 then 1 else iterfib (4 - 1, 1 + 1, 1)
--> iterfib (3, 2, 1)
--> if 3 = 1 then 2 else iterfib (3 - 1, 2 + 1, 2)
--> iterfib (2, 3, 2)
--> if 2 = 1 then 3 else iterfib (2 - 1, 3 + 2, 3)
--> iterfib (1, 5, 3)
--> if 1 = 1 then 5 else iterfib (1 - 1, 5 + 3, 5)
--> 5

末尾再帰的fact

let rec tailfact (n, res) = (* res には *)
    if n = 1 then res
    else tailfact (n - 1, n * res);;

これは末尾再帰的(再帰呼出しがelse以下の末尾呼び出し)。

tailfact (4, 1)を trace してみよう。

# tailfact (4, 1);;
tailfact <-- (4, 1)
tailfact <-- (3, 4)
tailfact <-- (2, 12)
tailfact <-- (1, 24)
tailfact --> 24
tailfact --> 24
tailfact --> 24
tailfact --> 24
- : int = 24

let rec iterfact (i, res, n) =
  if i = n + 1 then res
  else iterfact (i + 1, res * i, n);;

# iterfact (1, 1, 4);;
iterfact <-- (1, 1, 4)
iterfact <-- (2, 1, 4)
iterfact <-- (3, 2, 4)
iterfact <-- (4, 6, 4)
iterfact <-- (5, 24, 4)
iterfact --> 24
iterfact --> 24
iterfact --> 24
iterfact --> 24
iterfact --> 24
- : int = 24

以上、末尾再帰関数は処理中に逐一計算してくれてスタックに処理が溜まらないようにしている。

これを素朴に定義したfactと比べてみよう。

let rec fact n =
    if n = 1 then 1 else fact (n - 1) * n;;

# fact 4;;
fact <-- 4
fact <-- 3
fact <-- 2
fact <-- 1
fact --> 1
fact --> 2
fact --> 6
fact --> 24
- : int = 24

値を受け取ってもスタックに積むだけで最後に値を返すときまで計算してくれてないことがわかる。

高階関数

これまでの関数定義

let f パターン = 式

は、

let f = fun パターン -> 式

の略記。この略記法を知っておこう。

3.6.3節で

let rec sum_of (f, n) =
    if n = 0 then 0
    else sum_of (f, n - 1) + f n;;

をカリー化した定義

let rec sum_of f n =
    if n = 0 then 0
    else f n + sum_of f (n - 1);;

が現れる。sum_ofのあとに仮引数が()無しで2つ現れている。

仮引数を組にしない書き方の説明はこの後の「関数定義構文の拡張」というところで紹介される(ちょっと説明が前後している)。

fun パターン1 -> fun パターン2 -> ... -> fun パターンn -> e

は、

fun パターン1 パターン2 ... パターンn -> e

と書いてよい。letがあっても同様。つまり先ほどのsum_of:

let rec sum_of f n = ...

は、

let rec sum_of = fun f -> fun n ->  ...

の略記。

練習問題 4.4

# let s x y z = x z (y z);;
val s : ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>
# let k x y = x;;
val k : 'a -> 'b -> 'a = <fun>

このとき、s k kは恒等関数。処理を追えば明らか。

s k k 1
--> k 1 (k 1)
--> 1

練習問題 4.3

funnyという関数を考える。

let id x = x;; (* id: 恒等関数 *)
let ( $ ) f g x = f ( g x );; (* $: 関数の合成 *)

let rec funny f n =
  if n = 0 then id
  else if n mod 2 = 0 then funny (f $ f) (n / 2)
  else funny (f $ f) (n / 2) $ f;;

この謎の関数funny f nはどのような関数か調べよう。処理をトレースすると、

funny f 4
--> funny (f $ f) 2
--> funny ((f $ f) $ (f $ f)) 1
--> funny (((f $ f) $ (f $ f)) $ ((f $ f) $ (f $ f))) 0 $ ((f $ f) $ (f $ f))
--> id $ ((f $ f) $ (f $ f))
--> ((f $ f) $ (f $ f))

funny f 5
--> funny (f $ f) 2 $ f
--> (funny ((f $ f) $ (f $ f)) 1) $ f
--> ((funny (((f $ f) $ (f $ f)) $ ((f $ f) $ (f $ f))) 0) $ ((f $ f) $ (f $ f))) $ f
--> id $ ((f $ f) $ (f $ f)) $ f
--> ((f $ f) $ (f $ f)) $ f

repeatと同じ働きをしそう。数学的帰納法で示す。

証明

を 回合成したものを とする。

このときfunny f nは 回の合成f $ f $ ... $ fとなるか？

とする。 の偶奇で場合分けしよう。 1. (偶数)のとき、 は奇数であるから、 の定義の仕方から、

ただし、プログラム中の/の演算は商を求める計算なので奇数を2で割るときには注意。余りは切り捨てられるので、たとえば となる。

1. (奇数)のとき、 は偶数だから、

日記

断酒23日目。

「プログラミング in OCaml」がおもしろい。説明がうまいのと、練習問題も難易度が適切で、いまのところ読めてる。