Objective Caml 入門 手習い（3章 続き、4章）

Exercise 11-3,4

問題

Exercise11 以下の関数を定義せよ
3. 末尾再帰的関数を使ってフィボナッチ数を計算する fib_iter． (fib_pairを元にするとよい．)
4. 与えられた文字列のなかで ASCII コードが最も大きい文字を返す max_ascii 関数．文字列から文字を取出す方法は 2.2.5 節を参照のこと．
(この問題は意図的に「なにかが足りない」ように設定して あります．欲しい機能・関数があればマニュアルを調べたり，プログラム上で 工夫してください．)

自分の答え

(* Exercise 11-3 *)
(* 2回呼び出しの場合。 O(2^n)となる *)
let rec fib = function
  | 1 | 2 -> 1
  | n -> fib (n-1) + fib (n-2)

(* 末尾再起の場合。O(n) *)
let rec fib n p c =
  if n = 1 then c + p
  else fib (n-1) c (c+p)
;;

(* Exercise 11-4 *)

llet max_ascii str =
  let rec max_char n max_c =
	if n = 0 then max str.[n] max_c
	else max_char (n-1) (max max_c str.[n])
  in
  max_char (String.length str - 1) str.[0]
;;

Printf.printf "max_ascii -> %c\n" (max_ascii "abcdzefg")

Exercise 12

問題

Exercise12 neg を単独で用いる必要がなければ，pos と neg は一つの関数に まとめることができる．一つにまとめて定義せよ．

自分の答え

open Printf

(* Exercise 12 *)
let rec pos n =
  neg (n-1) +. 1.0 /. (float_of_int (4 * n + 1))
and neg n =
  if n < 0 then 0.0
  else pos n -. 1.0 /. (float_of_int (4 * n + 3))

let rec arctan1 ret = function
  |	0 -> ret
  |	n when n < 0 -> 0.0
  |	n when n mod 2 = 1 -> arctan1 (ret +. 1.0 /. (float_of_int (2 * n - 1))) (n-1)
  |	_ -> arctan1 (ret -. 1.0 /. (float_of_int (2 * n - 1))) (n-1)
;;

let arctan1 = arctan1 0.0;;

Printf.printf "%f\n" (4.0 *. (arctan1 1000000));;
Printf.printf "%f\n" (4.0 *. (pos 1000000));;

Exercise 1

問題

Exercise1 実数上の関数 f に対して ∫abf(x)dx を計算す る関数 integral f a b を定義せよ．またこれを使って， ∫0πsinx dx を計算せよ．
Exercise2 pow 関数をカリー化して定義せよ． 次に第一引数が指数になるよう(pow n x)に定義し，3乗する関数 cube を部分適用で 定義せよ．指数が第二引数であるように定義されている場合 (pow x n)，cube を pow から定義するには どうすればよいか?

自分の答え

open Printf

(* Exercise 1 *)

open Printf

(* Exercise 1 *)

let integral n f a b =
  let trapezoid x y h = (x +. y) *. h /. 2.0 in
  let h = (b -. a) /. (float_of_int n) in
  let rec sigma f n sum =
    if n = 0 then sum
    else
      let x' = f (a +. (float_of_int (n-1)) *. h)
      and y' = f (a +. (float_of_int n) *. h) in
        sigma f (n-1) (sum +. trapezoid x' y' h)
  in
  sigma f n 0.0
;;

let integral = integral 10000000;;

let integral_sin = integral sin;;

let print_integral_sin a b =
  Printf.printf "sin : %f -> %f = %f\n" a b (integral_sin a b);;

let pi = 3.1415926;;
print_integral_sin 0.0 pi;;



(* Exercise 2 *)

let rec powi x n res =
  if n = 0 then res
  else powi x (n-1) (x *. res)
;;

let pow n x = powi x n 1.0;;
let cube = pow 3;;

let pow_ x n = powi x n 1.0;;
let cube_ x = pow_ x 3;;

let print_cube x = 
  Printf.printf "cube %f = %f\n" x (cube x);
  Printf.printf "cube_ %f = %f\n" x (cube_ x);
;;

print_cube 3.0;;

感想

末尾再帰にめちゃめちゃはまった。わかってしまうとなんかあっさりなんだけど。自分の感覚では、たぶんハマリポイントが2個あって、1つはどうやって値を戻すか、もう1つはどうやって状態を保持するか。

let rec fact n ret =
  if n = 1 then ret (* 最終的にここまで来たところでretにためてきた値を戻す *)
  else fact (n-1) (n*ret) (* それまでは値を取り回し用引数に渡す *)
;;

値の戻し方は上に書いた通り、nを減らしていった場合は初期値まで来たところで戻す。それまでは取り回し用引数に渡し続ける。
あと気持ち悪いなあと自分で感じてたのは、retの内容。上からコードを読んでしまうから気持ち悪く感じてたんだろうけど、関数の宣言のところにあるretとn=1のところで戻るretは全く別物ってことをまず理解して、かつn-1のところでのretは初期値だ、ってことがわかれば普通に読める気がする。

あと第4章の問題の区分求積法のところは、台形近似してtrapezoidという関数を使っているけどこれ以外の近似もできるように、区分の求積関数は外出しにしたい。あとsigmaにおいてはbを全く使ってないので、これは書き直せるよね、と思った。あとで書き直す。

2010.03.23 追記

たくさん添削を頂きました！正しい解答に直しました。*1

*1:フィボナッチ数の2回呼び出し版と感想のfactで最後の括弧。あとmax関数。