プログラミング in OCaml 3rd chapter 練習問題を解いた

練習問題 3.1

1-3は解いたけどソース消えたので気が向いたらやる, 4は `String.capitalize_ascii` を使う邪道プレイした

練習問題 3.2

式 b1 && b2 を if式と true, false, b1, b2のみを用いて同じ意味になるように書き直しなさい。式 b1 || b2も同様に書き直しなさい。

という問題。trueもfalseもいらんな？と思いながら脳死で書いた

let and' b1 b2 = if b1 then b2 else b1;;
let or' b1 b2 = if b1 then b1 else b2;;

練習問題 3.3

ドモルガンの法則でやってあげるだけ

let and'' b1 b2 = not (not b1 || not b2);;
let or'' b1 b2 = not (not b1 && not b2);;

練習問題 3.4, 3.5

省略

練習問題 3.6

1

この問題sqrt使っていいのか・・・？

let geo_mean x y = sqrt (x * y);;

2

let bmi name t w =
  let bmi_index = w /. (t *. t) in
  let cond =
    if bmi_index < 18.5 then "やせ"
    else if bmi_index < 25.0 then "標準"
    else if bmi_index < 30.0 then "肥満"
    else "高度肥満" in
      name ^ "さんのBMIは" ^ cond ^ "です";;

3

let sum_and_diff (x, y) = (x + y, x - y);;
(* f( sum_and_diff (x, y)) = (x, y) になるようなf *)
let f (p, q) = ((p + q) / 2, (p - q) / 2);;

練習問題3.7

1

let pow x n =
  let rec calc (i, p) = if i = n then p else calc (i+1, p * x)
  in calc (0, 1);;

2

(*
  pow 1 1000000000;; 
  pow' 1 1000000000;;
  とかやったらpow'の方が早かったしいいっしょ(適当)
*)
let rec pow' x n =
  if n mod 2 = 0 then
    let c = pow' x (n / 2) in
    c * c
  else if n == 1 then x
  (* x ^ (2n + 1) = x * (x ^ 2n) = x * ((x ^ n) ^ 2) *)
  else x * pow' x (n - 1);;

練習問題 3.8

練習問題3.7.1が反復的な回答なので省略

練習問題 3.9

(* fact 4
  = cond ((4 = 1), 1 , 4 * fact (4 - 1))
  = cond (false, 1, 4 * fact(3))
  = cond (false, 1, 4 * (cond (false, 1, 3 * fact(2))))
  = cond (false, 1, 4 * (cond (false, 1, 3 * (cond ((2 = 1), 1, 2 * fact(1)))))
  ...
 *)

この問題は fact 4を考えるよりも fact 1を考えたほうがわかりやすい。

(* fact 1
  = cond ((1 = 1), 1 , 1 * fact (0)) <- n を 1に置き換えただけ、
  = cond (1, 1, 1 * (cond ((0 = 1), 1, 0 * fact (0 - 1)))
  ...
 *)

という風に基底部である n = 1の時に止まらない。
これは if式が条件式によってe1とe2のどちらかのみを評価するが、OCamlの評価戦略ではe1, e2共に評価されるようになっているためである。

練習問題 3.10

省略

練習問題 3.11

1

let gcd x y =
  let rec calc x y =
    if x mod y = 0 then y
    else calc y (x mod y)
  in
    if x > y then calc y x
    else calc x y;;

2

let comb n m =
  (* n * n - 1 * .. * k を返す関数, fact_k n 1 でn!を求めることができる*)
  let rec fact_k n k =
    if n = k then k
    else n * fact_k (n - 1) k
  in
    let numerator = fact_k n (n - m + 1)
    and denominator = fact_k m 1
    in
      numerator / denominator;;

3

let iterfib n =
  let rec calc a b c =
    if c == n then a + b
    else calc b (a + b) (c + 1)
  in
    calc 0 1 1;;

4

let max_ascii s =
  let l = String.length s
  in
    let rec calc c index =
      if l == index then c
      else calc (max s.[index] c) (index + 1)
    in
      calc s.[0] 0;;

解説記事書いてる人ってすごいんだな、と思った。(小並感)