• 日時 :2006/6/12 (Mon)
  • 場所 :名大 理学部1号館(多元数理科学研究科) 307室
  • 時刻 :18:00〜19:30
  • 参加者:9名
  • 話題 :
  • おつかれさまです。勉強会中でやった継続渡しによる別解を書きました。 -- けいご? 2006-06-12 (月) 21:27:18
  • すみません、Exeriseの更新をしようと思ったのですが、編集リンクを辿ると、凍結されていないのに「....は編集できません」という編集できない旨のj返事が返ってきます。どうしたもんでしょう...? -- 小笠原? 2006-06-19 (月) 17:52:20
  • すみません、直しました。 -- けいご? 2006-06-20 (火) 14:01:10

5章 Exercise 続き †

Exercise 6. けいご †

  • 元のquick
    let rec quick = function
        [] -> []
      | [x] -> [x]
      | x :: xs ->  (* x is the pivot *)
          let rec partition left right = function
              [] -> (quick left) @ (x :: quick right)
            | y :: ys -> if x < y then partition left (y :: right) ys
                         else partition (y :: left) right ys
          in partition [] [] xs;;
  • 答え
    let rec quicker l sorted = match l with
        [] -> sorted
      | [x] -> x :: sorted
      | x :: xs ->  (* x is the pivot *)
          let rec partition left right = function
              [] -> quicker left (x :: quicker right sorted)
            | y :: ys -> if x < y then partition left (y :: right) ys
                         else partition (y :: left) right ys
          in partition [] [] xs;;
  • 試してみる
    # quicker [2; 3; 9; 1; 5; 4] [];;
    - : int list = [1; 2; 3; 4; 5; 9]
  • quicker left (x :: quicker right sorted)がポイント
  • Haskellのshowsもこんな感じ 一般にconsリストの連結は時間効率が悪いので末尾をλで抽象する。
    • (Haskellで書くと) "hoge" ++ "foobar" よりも (?s -> 'h':'o':'g':'e':s) "foobar" のほうが早い。
    • (関係ないけど) しかし、stringはchar listではない…試してみて気づいた。
      # (fun x -> 'h'::'o'::'g'::'e'::x) "foobar";;
      This expression("foobar") has type string but is here used with type char list

Exercise 7. みずの &dagger;

(* fromからtoまでの数列を生成 *)
let rec range from_value to_value = 
   if from_value > to_value then []
   else from_value::(range (from_value + 1) to_value);;

(* 整数版sqrt *)
let sqrt_int x = int_of_float (sqrt (float_of_int x));;

let f r x xs= let y = sqrt_int(r - x*x) in
             if x > y && (x*x + y*y = r) then
                (x,y)::xs
             else
                 xs;;

let squares r = List.fold_right (f r) (range 0 (sqrt_int r)) [];;

Exercise8.飯田、吉岡 &dagger;

let rec rev l1 l2 = match l1 with [] -> l2
                  | x::rest -> rev rest (x::l2);;
let map2 f = let rec map'f res
           = function [] -> rev res [] | x::rest -> map' f((f x)::res) rest
           in map' f [];;

Exercise8の別解 by けいご &dagger;

継続渡しスタイル (Continuation Passing Style)と呼ぶこともあります。

  • OCaml:
    let map2 f xs = 
      let rec map' f ys k = 
        match ys with
            []      -> k [] 
          | y'::ys' -> map' f ys' (fun zs -> k (f y'::zs))
      in map' f xs (fun x->x);;
    ここで
         | y'::ys' -> map' f ys' (fun zs -> f y' :: k zs)
    とやってしまった。結果リストが逆順になる…thx to みずの
  • Haskell脳なかわいそうな人のために:
    map' f (x:xs) k = map' f xs (?ys->k (f x:ys))
    map' f []     k = k []

効率は? &dagger;

どうやって計る?体感的には同じ位に思えた。

とりあえず,ベンチマークしてみました.(樋口)

教科書中にあった指定した長さの乱数のリストを得る関数

let nextrand seed =
  let a = 16807.0 and m = 2147483647.0 in
  let t = a *. seed
  in t -. m *. floor(t /. m)
let rec randlist n seed tail =
  if n = 0 then (seed,tail)
  else randlist (n-1) (nextrand seed) (seed::tail)

これを使い,長さ10000000のリストを用意し, すべての要素を+1するような実験を行いました.

let _ = map2 (fun x -> x +. 1.0) (snd (randlist 10000000 1.0 []));;

ex8a, ex8bは共にocamlc.opt -o ex8a ex8a.ml といったように特にオプションなしでコンパイルしました.

  • ex8a 飯田・吉岡 解
           Command being timed: "./ex8a"
           User time (seconds): 18.46
           System time (seconds): 0.68
           Percent of CPU this job got: 99%
           Elapsed (wall clock) time (h:mm:ss or m:ss): 0:19.31
           Average shared text size (kbytes): 0
           Average unshared data size (kbytes): 0
           Average stack size (kbytes): 0
           Average total size (kbytes): 0
           Maximum resident set size (kbytes): 0
           Average resident set size (kbytes): 0
           Major (requiring I/O) page faults: 163
           Minor (reclaiming a frame) page faults: 114564
           Voluntary context switches: 0
           Involuntary context switches: 0
           Swaps: 0
           File system inputs: 0
           File system outputs: 0
           Socket messages sent: 0
           Socket messages received: 0
           Signals delivered: 0
           Page size (bytes): 4096
           Exit status: 0
  • ex8b けいご 解
           Command being timed: "./ex8b"
           User time (seconds): 19.82
           System time (seconds): 3.68
           Percent of CPU this job got: 11%
           Elapsed (wall clock) time (h:mm:ss or m:ss): 3:31.57
           Average shared text size (kbytes): 0
           Average unshared data size (kbytes): 0
           Average stack size (kbytes): 0
           Average total size (kbytes): 0
           Maximum resident set size (kbytes): 0
           Average resident set size (kbytes): 0
           Major (requiring I/O) page faults: 30614
           Minor (reclaiming a frame) page faults: 628565
           Voluntary context switches: 0
           Involuntary context switches: 0
           Swaps: 0
           File system inputs: 0
           File system outputs: 0
           Socket messages sent: 0
           Socket messages received: 0
           Signals delivered: 0
           Page size (bytes): 4096
           Exit status: 0

User timeを見ると似たようなものですけど, System timeやpage faultをみてみると ex8bは,激しくメモリを消費中?

6章 Exercise &dagger;

Exercise 2(樋口) &dagger;

  nat上で
   int_of_nat,
   mul,
   monus を定義せよ 
参考 nat の定義
 type nat = Zero | OneMoreThan of nat ;;
let rec int_of_nat = function
  Zero -> 0 |
  OneMoreThan n -> 1 + int_of_nat n;;
let rec add m n =
 match m with
   Zero -> n |
   OneMoreThan m' -> OneMoreThan (add m' n);;
が定義されているとして

let rec mul m n =
 match m with 
  Zero -> Zero |
  OneMoreThan Zero -> n |
  OneMoreThan m' -> add n (mul m' n);;
 
let rec monus m n = 
 match m with
   Zero -> Zero |
   OneMoreThan m' -> match n with
                      Zero -> OneMoreThan m' |
                      OneMoreThan n' -> monus m' n';;

Exercise 3(末次) &dagger;

let rec minus m n = 
  match (m, n) with 
      (m, Zero)  -> Some m
    | (Zero, _) -> None
    | (OneMoreThan k, OneMoreThan l) -> minus k l;;

Exercise 5(下村) &dagger;

(* inord *)
let rec inord t l =
  match t with
      Lf -> l
    | Br(x,left,right) -> (inord left (x :: inord right l));;
(* postord *)
let rec postord t l =
  match t with
      Lf -> l
    | Br(x,left,right) -> (postord left (postord right (x::l)));;

一応、ここで使った二分木の定義。

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;

Exercise 6(小笠原) &dagger;

ごめんなさい、結構難しい...ToT すぐにできないので、宿題とさせてください。


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2008-09-27 (土) 20:31:10 (4412d)