2014-04-14

 昨日から不動点コンビネータまわりで詰まっている。よくわからないなぁと思ってだらだら調べて一応は書けてしまったので、次に進んでもいいのだけど、あまり意味が理解できていない。

let rec fix f x = f (fix f) x;;

を用いて再帰関数をfixのみの再帰で定義しなさいというもの。

仕組みがよくわかっていないが、これで動く:

let fact_fix n =

  fix (fun f x -> if x=0 then 1 else x * f (x-1)) n;;

もう少し冗長に書くとこう(こっちで紹介している人のほうが多い):

let fact_f f x =

  if x=0 then 1 else x * f (x-1);;

let fact_fix = fix fact_f;;

意味的には後者のほうが理解しやすいかもしれない。両者の操作は同じ。

つまるところ、fixの機能だけを取り出すならば、「第一引数として受け取った関数を再帰させる」ということになる。そんなこと言われてもどうするんだ。

 前者の定義による計算を真面目に追ってみる(以下fun f x -> ...をFと書く):

fact_fix 5

= fix F 5

= F (fix F) 5

= 5 * (fix F 4)

= 5 * (F (fix F) 4)

= 5 * 4 * (fix F 3)

...

= 5 * ... * 1 * (fix F 0)

= 5 * ... * 1 * (F (fix F) 0)

= 5 * ... * 1 * 1

= 120

 なんとなくわかった気がする。少し悩んでいたのは、3行目"(fix F)"の扱いがよくわからなかったから。これそもそも「引数をひとつ取る関数」として引数になっているから、評価すべきは先頭のFであって、それに従えばちゃんと「引数をひとつ取る関数」に引数(4行目の4)が与えられるわけです。評価順序をちゃんと考えてなかった。Fは再帰関数本体ではなくて、再帰させる関数とその引数を受け取る関数。fixはそのFを再帰させる関数ということ。ちなみにFの内側のfは引数いくつでもOK。gcdは:

let gcd_byfix n m =

  fix (fun f n m ->

    if n mod n = 0 then m else f m (n mod m)) n m;;

となる。

 ってこれ先学期やったはずなんですけどね……。だいたいわかった気がするからいいか。

 今日は2限出て5限出た。回帰分析があまりよくわかっていなかった。

広告を非表示にする