活動記録/第7回のバックアップ(No.4)

予定のみ &dagger;

日時　：2006/6/26 (Mon)
場所　：名大理学部1号館(多元数理科学研究科) 307室
時刻　：18:00～19:30
参加者：??名

↑

Chapter 6. Exercise続き &dagger;

↑

Chapter 7. Exercise &dagger;

↑

Exercise 1 &dagger;

ref型を

type 'a ref = { mutable contents : 'a};;

こんな定義の更新可能レコードと見て，関数ref, 前置演算子!, 中置演算子:= をレコード操作で書け．

関数ref

# let ref x = { contents = x } ;;
val ref : 'a -> 'a ref = <fun>

前置演算子!

# let ( ! ) x = x.contents ;;
val ( ! ) : 'a ref -> 'a = <fun>

中置演算子:=

# let ( := ) x y = x.contents <- y;;
val ( := ) : 'a ref -> 'a -> unit = <fun>

↑

Exercise 2 &dagger;

整数の参照をインクリメントする関数incr

# let incr x = x := !x + 1;;
val incr : int ref -> unit = <fun>

↑

Exercise 3 &dagger;

# let f = ref (fun y -> y+1)
  let funny_fact x = if x = 1 then 1 else x * (!f(x-1));;
# f := funny_fact;;
# funny_fact 5;;

let fは単に関数の参照が用意したいだけで，funで定義された関数の中身に意味は無い．
f := funny_factによりfがfunny_factをさすようになる．
その結果，funny_factの定義中の!fが自分自身(funny_fact)を呼ぶ事になり，
階乗を素直に再帰的に定義した時と同じ形になっている．

↑

Exercise 4 &dagger;

# let fact_imp n =
   let i = ref n and res = ref 1 in
    while ( !i > 0 ) do
     res := !res * !i;
     i := !i - 1
    done;
    !res;;
val fact_imp : int -> int = <fun>

↑

Exercise 5 &dagger;

↑

Exercise 6 &dagger;

↑

Exercise 7 &dagger;

↑

Exercise 8 (末次) &dagger;

まず元の定義

let rec change = function
    (_, 0) -> []
  | ((c :: rest) as coins, total) ->
      if c > total then change (rest, total)
      else c :: change (coins, total - c) ;;

これだと

let us_coins = [25; 10; 5; 1]
and gb_coins = [50; 20; 10; 5; 2; 1];;

change (gb_coins, 43);;
change (us_coins, 43);;

は成功するが、

change ([5; 2], 16);;
Exception: Match_failure ("", 66, -211).

となって失敗する．これは大きい額から試していくので 5 で3回割ったあと、リストの最後 nil まで行って、 ([], 1) にマッチする規則が無いため．

そこで失敗したら戻って小さな額で割るようにすればよい．

let rec change = function
    (_, 0) -> []
  | ((c :: rest) as coins, total) ->
      if c > total then change (rest, total)
      else
	 (try
	      c :: change (coins, total - c)
	  with Failure "change" -> change (rest, total))  (* 失敗したら c で割るのを諦めて次に小さい数で続ける *)
  | _ -> raise (Failure "change");;  (* ([], 1以上) のときは例外を投げる *)

このようにすれば

change ([5; 2], 16);;
- : int list = [5; 5; 2; 2; 2]

と計算できる．

活動記録/第7回 のバックアップ(No.4)

予定のみ &dagger;

Chapter 6. Exercise続き &dagger;

Exercise 1 &dagger;

Exercise 6 (小笠原) &dagger;

Exercise 7 &dagger;

Exercise 8 &dagger;

Exercise 9 (けいご) &dagger;

Chapter 7. Exercise &dagger;

Exercise 1 &dagger;

Exercise 2 &dagger;

Exercise 3 &dagger;

Exercise 4 &dagger;

Exercise 5 &dagger;

Exercise 6 &dagger;

Exercise 7 &dagger;

Exercise 8 (末次) &dagger;

活動記録/第7回のバックアップ(No.4)