- 日時 :2006/6/12 (Mon) - 場所 :名大 理学部1号館(多元数理科学研究科) 307室 - 時刻 :18:00〜19:30 - 参加者:9名 - 話題 : - おつかれさまです。勉強会中でやった[[継続渡しによる別解:http://tsukimi.agusa.i.is.nagoya-u.ac.jp/~sydney/ocaml/index.php?%B3%E8%C6%B0%B5%AD%CF%BF%2F%C2%E85%B2%F3#k36863d8]]を書きました。 -- [[けいご]] &new{2006-06-12 (月) 21:27:18}; - すみません、Exeriseの更新をしようと思ったのですが、編集リンクを辿ると、凍結されていないのに「....は編集できません」という編集できない旨のj返事が返ってきます。どうしたもんでしょう...? -- [[小笠原]] &new{2006-06-19 (月) 17:52:20}; - すみません、直しました。 -- [[けいご]] &new{2006-06-20 (火) 14:01:10}; - ghqygGUTIv -- [[sejcuenmfqn]] &new{2008-09-23 (火) 10:36:01}; - YmqeXcQsbt -- [[xtddes]] &new{2008-09-26 (金) 22:50:18}; #comment ---- #contents * 5章 Exercise 続き [#e8ab579a] **Exercise 6. けいご [#k186bd76] - 元の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. みずの [#a2b0a0db] (* 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.飯田、吉岡 [#x53ada9d] 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 けいご [#k36863d8] '''継続渡しスタイル (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 [] ***効率は? [#d340c6ec] どうやって計る?体感的には同じ位に思えた。 とりあえず,ベンチマークしてみました.(樋口) ~教科書中にあった指定した長さの乱数のリストを得る関数 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 [#j2d045ed] **Exercise 2(樋口) [#vfa96a64] 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(末次) [#pb712e62] let rec minus m n = match (m, n) with (m, Zero) -> Some m | (Zero, _) -> None | (OneMoreThan k, OneMoreThan l) -> minus k l;; **Exercise 5(下村) [#s9e70b19] (* 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(小笠原) [#o9117959] ごめんなさい、結構難しい...ToT すぐにできないので、宿題とさせてください。