「プログラミング in OCaml」をF#で(2)

今日も元気に進めていきたいと思います。4章だけです。全然進まないので、この日記をつけていなければすでに断念していた自信がある。

P76 OCamlの型推論は完全性「変数宣言に": int"などの型の注釈をつけても型がつくのであれば、省略しても必ず型推論が成功する」を備えている、という話なんだけど、F#の場合、型注釈無しの

let rec pow x n = if n = 1 then x else x * pow x (n - 1)

だと、int -> int -> int になるが、型注釈をつけて

let rec pow (x:float) n = if n = 1 then x else x * pow x (n - 1)

だと、float -> int -> float になる。型推論の結果が違うのも"成功"というのか、F#の型推論は完全性を備えていないのかどちらなんだろうか。「x * pow x (n - 1)」を「x *. pow x (n - 1)」にすれば型注釈なくても float -> int -> float になるんだけど、警告が発せられるし……。
P82
- 4.2。0のときの処理が……。

let rec repeat f n x = if n > 0 then repeat f (n - 1) (f x) else x
let fib n = 
  let (fibn, _) =
    if n = 0 then (0, 0) else
    let infib (f1, f2) = (f1 + f2, f1) in repeat infib (n - 1) (1, 0)
  in fibn

- 4.3。fをn回呼び出す関数を返す？
- 4.4。k 1 (k 1) になって、k は fun x y -> x なんで、x にあたる1が返る？
- 4.5。あー、なんかちゃんと読んでたつもりなのに、関数が値に評価されずに関数のままで計算ステップを考えるやり方がよくわからない……。と思ったけど、無名関数で地道に置き換えてったら出来た気がした。fun を消すときに、実際の引数も一緒に消してけば良いのか。twiceは fun f x -> f (f x)
  - twice twice f x
  - twice (fun x -> f (f x)) x
  - (fun x -> f (f x)) ((fun x -> f (f x)) x)
  - (fun x -> f (f x)) (f (f x))
  - f (f (f (f x)))
- 4.6。KコンビネータとSコンビネータがこういう感じで定義されていて、

let k x y = x
let s x y z = x z (y z)

- kとsの関数適用のみで fun x y -> y 相当を表現せよ、という問題なんだけど、答えは多分 k (s k k)。わからないのは、A.何故これが fun x y -> y なのか？と、B.あてずっぽうでなしにこれを導くにはどうすれば良いのか？という点。A.に関しては、計算ステップを考えればいけるのかなぁと思うんだけど
  - まず、s k k は fun x -> x である事を知っているので、
  - fun x y -> x
    - # ↑の k の定義の x に fun x -> x を適用(でもこの x は別物の x なので、z としておく)。y はまだわたされていない
  - fun y -> (fun z -> z)
    - # 右で展開させたら左からは消して良いのかな？
  - これが何を意味しているのか、というと、引数yをもらうと、引数にもらった値をそのまま返す関数を返す、ということになるのではないか
  - k (s k k)に引数を一つ渡すと、引数をそのまま返す関数になるので、返された関数に二つ目の引数が渡される。そうすると、二つ目の引数がそのまま返る
  - これは、fun x y -> y の動きと同じ
  - ああ、これがカリー化関数の話なのか、とも思うけど、ちょっとしっくりこないというか、わからん……
  - B.あてずっぽう以外でこれを導く方法は全然わからない