- 追加された行はこの色です。
- 削除された行はこの色です。
- 日時 :2006/6/5 (Mon)
- 場所 :名大 理学部1号館(多元数理科学研究科) 309室
- 時刻 :18:00〜19:30
- 参加者:12名
- 話題 :
-- hoge
-- foo
-- bar
#comment
----
#contents
* 5章 Exercise [#bfc2aa87]
**Exercise 1. 樋口 [#ge7486ac]
1. [[]]
'a list list
2. [[1;3]; ["hoge"]]
NG
3. [3] :: []
int list list
4. 2 :: [3] :: []
NG
左からみてくと一見良さそうだけど,:: が右結合なので int list list に int をpush_frontしようとしている事になってしまう.
(2 :: [3]):: [] ならOK
5. [] :: []
'a list list
6. [(fun x -> x) ; (fun b -> not b) ]
(bool -> bool) list
**Exercise 2. 小笠原 [#g00c6393]
(以下3行は前提とする関数)
let hd (x :: rest) = x
let tl (x :: rest) = rest
let null = function [] -> true | _ -> false
ここから本題。 match を使わずにリスト操作しようとすると
如何に大変かを体験してくださいという問題 :)
let rec sum_list l =
if null l then 0
else (hd l) + (sum_list (tl l))
let rec max_list l =
if null (tl l) then hd l
else
let n1 = hd l
and n2 = hd (tl l)
and rest = tl (tl l) in
if n1 > n2 then max_list (n1 :: rest)
else max_list (n2 :: rest)
n1,n2,rest のバインディングとか面倒そのもの。
match を使えばもっと簡単。
でも実はリスト以外の構造(キューとかスタックとか木とか)には
先頭要素を取り出すパターンとかないので、
やっぱり面倒なことを書かなくてはいけない罠.
(リストが簡単になるだけでも効果絶大だけど)
**Exercise 3. 下村、山畑 [#j706ae3a]
***4 [#i203085e]
fold_leftを使ったもの。引数なしで定義すると…。
let concat = List.fold_left (@) [];;
この時のコンパイラの出力。
# val concat : '_a list list -> '_a list = <fun>
'_aに関しては第3回のページを参照。
これはOCamlの参照という機能を使えるようにするための制限だとか。
実際に引数を与えると型が固定される。
# concat [[1;2];[3;4]];;
- : int list = [1; 2; 3; 4]
# concat;;
- : int list list -> int list = <fun>
#
多相性を持たせるには引数を付ければよい。
let concat list = List.fold_left (@) [] list;;
同じく、この時のコンパイラの出力。
val concat : 'a list list -> 'a list = <fun>
***5 [#cc42e37c]
let rec zip s1 s2 =
match s1 with
[] -> []
| x::xs -> match s2 with
[] -> []
| y::ys -> (x,y) :: zip xs ys;;
matchに組を使うと見やすくなる。(括弧はいらないとのこと。)
let rec zip' s1 s2 =
match s1,s2 with
[],_ -> []
| _,[] -> []
| x::xs,y::ys -> (x,y) :: zip' xs ys;;
***6-a [#za7320cc]
let rec belong a s =
match s with
[] -> false
| x::xs -> if x = a then true else belong a xs
***6-b [#j23b1206]
問題文をそのまま書いたもの。
let rec intersect s1 s2 =
match s1 with
[] -> []
| x::xs -> if belong x s2
then x :: intersect xs s2
else intersect xs s2;;
filterを使ったもの。
let intersect' s1 s2 =
filter (fun x -> belong x s1) s2;;
***6-c [#e0a93f70]
問題文をそのまま書いたもの。
let rec union s1 s2 =
match s1 with
[] -> s2
| x::xs -> if belong x s2
then union xs s2
else x :: (union xs s2);;
filterを使ったもの。
let union' s1 s2 =
s1 @ filter (fun x -> not (belong x s1)) s2;;
***6-d [#f1767059]
問題文をそのまま書いたもの。
let rec diff s1 s2 =
match s1 with
[] -> []
| x::xs -> if belong x s2
then diff xs s2
else x :: diff xs s2;;
filterを使ったもの。
let diff' s1 s2 =
filter (fun x -> not (belong x s2)) s1;;
**Exercise 5. よしひろ [#f105e7db]
let forall' prop l = fold_right (&&) (map prop l) true
let exists' prop l = fold_right (||) (map prop l) false
↑fold_rightとmapを使った方法。(問題にはfold_rightとmapを使えと書いてあった。)
しかしこれだとリストlを何度もみながら計算するので効率がいいとはいえない。
↓は小笠原さんによる改良versionである。(違ったら指摘してください。)
let forall'' prop l =
fold_right (fun x b -> b && prop x) l true
let exists'' prop l =
fold_right (fun x b -> b || prop x) l false
(OK です. 実用的には、fold_leftの方がいいかも. tail recursive だし. by小笠原)
**Exercise 6. けいご [#k186bd76]