• 日時 :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. 小笠原 †

(以下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. 下村、山畑 †

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 &dagger;

 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 &dagger;

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

6-b &dagger;

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

 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 &dagger;

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

 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 &dagger;

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

 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. よしひろ &dagger;

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

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2008-09-23 (火) 22:08:50 (4413d)