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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 活動記録/第4回 へ行く。
  • 1 (2006-06-05 (月) 14:42:35)
  • 2 (2006-06-05 (月) 14:46:05)
  • 3 (2006-06-05 (月) 22:34:04)
  • 4 (2006-06-06 (火) 11:35:59)
  • 5 (2006-06-06 (火) 11:35:59)
  • 6 (2007-11-27 (火) 14:40:25)

---

• 日時　：2006/6/5 (Mon)
• 場所　：名大 理学部1号館(多元数理科学研究科) 309室
• 時刻　：18:00〜19:30
• 参加者：12名
• 話題　：
  • hoge
  • foo
  • bar

お名前:

---

5章 Exercise †

Exercise 1. 樋口 †

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. 小笠原 †

(以下３行は前提とする関数)
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. 下村、山畑 †

4 †

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 †

 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 †

 let rec belong a s =
   match s with
       [] -> false
     | x::xs -> if x = a then true else belong a xs

6-b †

問題文をそのまま書いたもの。

 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 †

問題文をそのまま書いたもの。

 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 †

問題文をそのまま書いたもの。

 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. よしひろ †

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小笠原)