プログラミング in OCaml #8

http://d.hatena.ne.jp/kengpong/20091107/p1

(* 練習問題 5.2 次の関数を定義しなさい *)
(* 1. 正の整数 n から 1 までの整数の降順リストを生成する downto1 *)
let rec downto1 = function
    0 -> []
  | n -> n :: downto1 (n - 1);;

(* 2. 関数 roman *)
let rec roman dict n =
    match dict with
    [] -> ""
  | (n', s) :: rest when n >= n' -> s ^ roman dict (n - n')
  | (n', s) :: rest -> roman rest n;;

(* 3. 与えられたリストのリストに対し、(内側の)要素数を返す nested_length *)
let rec nested_length = function
    [] -> 0
  | x :: rest -> (List.length x) + nested_length rest;;

(* 4. 与えられたリストのリストに対し、内側のリストの要素を並べ変えたリストを返す concat *)
let rec concat l = List.fold_left (@) [] l;;

(* 5. zip *)
let rec zip l1 l2 =
    match (l1, l2) with
    | (x :: xrest, y :: yrest) -> (x, y) :: zip xrest yrest
    | (_, _) -> [];;

(* 6. unzip *)
let rec unzip = function
    [] -> ([], [])
  | (x, y) :: rest -> let (xrest, yares) = unzip rest in (x :: xrest, y :: yrest);;

(* 7. リストとリストの要素上の述語 p を満すすべての要素のリストを返す filter *)
let rec filter f = function
    [] -> []
  | x :: rest when f x -> x :: filter f rest
  | x :: rest -> filter f rest;;

(* 8-1. 先頭から n 番目までの要素からなる部分リストを取りだす take *)
let rec take n = function
    x :: rest when n > 0 x :: take (n - 1) rest
  | _ -> [];;

(* 8-2. 先頭から n 番目までの要素を抜かした部分リストを取りだす drop *)
let rec drop n = function
    x :: rest when n > 0 -> drop (n - 1) rest
  | l -> l;;

(* 9. (空でない) リストのなかから最大値を返す max_list *)
let max_list = function
    x :: [] -> x
  | x :: rest -> let y = max_list rest in if x > y then x else y;;

日が空いた上に、 半分寝てるような状態でやったので、いろいろと駄目っぽいなー。
気がついた点として

• concat の効率が悪い
• さらっと List モジュール使ってるけど、いいの?
• ガードと if 式の使いわけが気分で分けてる感じになっちゃってるけど、どうしよう。

とかがあるかなー。

とりあえずは動けばあんまり気にしない方向で!*1

*1:もちろんツッコミ等は大歓迎です

プログラミング in OCaml #7

プログラミング in OCaml (目次) - kengpong

(* 練習問題 4.1 uncurry を定義 *)
let curry f x y = f (x, y);;
let average (x, y) = (x +. y) /. 2.0;;
let curried_avg = curry average;;

let uncurry f (x, y) = f x y;;
let avg = uncurry curried_avg in avg (4.0, 5.3);;

(* 練習問題 4.2 repeat を使って fib を定義 *)
let rec repeat f n x =
    if n > 0 then repeat f (n - 1) (f x) else x;;

let fib n =
    let (fibn, _) =
        repeat (fun (x, y) -> (x + y, x)) n (0, 1)
    in fibn;;

(* 練習問題 4.6 関数 fun x y -> y を コンビネータ s と k を組合せて表現 *)
let f x y = k (s k k) x y;;

うーん、だんだん難しくなってきたなー。
4.6 は全くわからなかったのでカンニング。
答え見てもパッと見だと全くわからないところが面白い

プログラミング in OCaml #6

プログラミング in OCaml (目次) - kengpong

(*
 * 練習問題 3.13
 * 練習問題 3.7 の pow 関数をカリー化して定義せよ。
 *)
let rec pow x n =
    if n < 2 then x
    else pow x n - 1 *. x;;

(* 第一引数が指数になるように定義し、3乗する関数 cube を部分適用で定義 *)
let rec pow n x =
    if n < 2 then x
    else pow (n - 1) x *. x;;
let cube = pow 3;;

(* 第二引数が指数の場合に、cube を定義するにはどうするか *)
let rec pow x n =
    if n < 2 then x
    else pow x n - 1 *. x;;
let cube = (fun x -> pow x 3);;

(* 練習問題 3.14 *)
(* え?定積分?なにそれうまいの? *)

(* 練習問題 3.15 以下の型の適当な関数を定義 *)
(* int -> int -> int -> int *)
let foo i j k = i + j + k;;

(* (int -> int) -> int -> int *)
let bar (f : int -> int) i = f i;;

(* (int -> int -> int) -> int *)
let baz (f : int -> int -> int) = f 1 2;;

Newton-Raphson法のあたりは華麗にスルーした。いつか倒すリストに入れておいてやろう!

適当な関数を定義が適当すぎるのはこれで良いの?
なんか問題読み間違えてる気もするなぁ。

トラックバックの動作

自分の日記内にトラックバックを打った時に、トラックバックタイトルにブログタイトルが入る場合と入らない場合がある。
プログラミング in OCaml 連載でトラックバック一覧を見る時に入り乱れてるとすごく見にくい。
今の所は、ブログタイトル入ってたら打ち直すとかやってるけど、いいかげんめんどくさい。
どうにかなんないもんかなー。

プログラミング in OCaml #5

プログラミング in OCaml (目次) - kengpong

(* 練習問題 3.11 以下の関数を定義 *)
(* 1. ユークリッドの互除法で二整数の最大公約数を求める関数 gcd *)
let rec gcd(a, b) =
      if a mod b = 0 then b
      else gcd(b, a mod b);;

(* 2. 本文中で与えた再帰的な定義で nCm を求める関数 comb *)
let rec comb(n, m) =
    if m = 0 || n = m then 1
    else comb(n - 1, m) + comb(n - 1, m - 1);;

(* 3. 末尾再帰的関数を使ってフィボナッチ数を計算する iterfib *)
let fib n =
      let rec iterfib(i, x, y) =
          if n = i then x
          else iterfib(i+1, x + y, x)
      in
      iterfib(1, 1, 0);;

(* 4. 与えられた文字列の中で ASCII コードが最も大きい文字を返す max_ascii *)
let max_ascii str =
      let rec _max_ascii(i, max) =
          if i = String.length str then max
          else
              let len = int_of_char str.[i] in
              _max_ascii(i+1, if len > max then len else max)
      in
      char_of_int (_max_ascii (0, 0));;

1, 2 については、本当にそのまま書いたという感じ。おもすれー。
3 はちょっと悩んだ。まだまだ関数型の考えかたに慣れ無いなー。

後回しにしていたけども、標準的なコーディング規約ぐらいは知っておこうか。
インデントの数とか位置とか、カッコの前後のスペースとか、若干悩んでしまう。
あとは名前の付け方とかも慣例を知りたいなー。 _max_ascii みたいな名前ってどうよみたいな。

プログラミング in OCaml #4

プログラミング in OCaml (目次) - kengpong

(*
 * 練習問題 3.7
 * x は実数、n は0 以上の整数として、x**n を計算する関数 pow (x, n) を
 * 以下の2通りで定義しなさい。
 *)
(* 1. 計算中に pow の再帰呼び出しをn回伴う定義 *)
let rec pow (x, n) =
    if n < 2 then x
    else pow(x, n - 1) *. x;;

(* 2. 計算中の pow の再帰呼び出しが約 log2n 回ですむ定義 *)
let rec pow(x, n) =
    if n = 0 then 1.0
    else if n mod 2 = 0 then pow(x *. x, n / 2)
    else pow(x *. x, n / 2) *. x;;

(* 練習問題 3.8 指数関数を iterpow という名前で反復的的に定義しなさい *)
let pow(x, n) =
    let rec iterpow(x, n, res) =
        if n < 1 then res
        else iterpow(x, n - 1, res *. x)
    in    iterpow(x, n, 1.0);;

3.7-2 はカンニングした。冪乗 - Wikipediaにあるバイナリ法と呼ばれる手法らしい。

3.8 はすごく不安。こういう事で良いのか?

プログラミング in OCaml #3

プログラミング in OCaml (目次) - kengpong

(* 練習問題3.6 次の関数を定義せよ*)
(* 1. 2実数の相乗平均をとる関数 geo_mean *)
let geo_mean (x, y) = sqrt(x *. y);;

(*
 * 2. 名前(文字列)、身長(実数)、体重(実数)の組を受け取って
 * 「○○さんは痩せています」などの文字列を返す関 bmi
 *)
let bmi (name, height, weight) =
    let num = weight /. (height ** height) in
    let status =
        if num > 30. then
            "overweight"
        else if num > 25. then
            "normal"
        else
            "underweight"
       in
        name ^ ":" ^ status
;;

(* 3. 任意の整数 x, y に対し、 f (sum_and_diff (x,y)) が (x,y) を返す関数f *)
let sum_and_diff (x, y) = (x + y, x - y);;
let f (x, y) = ((x + y) / 2, (x - y) / 2);;

2. の問題は、最初日本語で出力しようと思ったのだけど、なんか上手くいかなかった。
その辺の日本語環境回りの事とかは、後々出てきたりするのかな?