活動記録/第4回 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• 活動記録/第4回 へ行く。
• 活動記録/第4回 の差分を削除

- 日時　：2006/6/5 (Mon)
- 場所　：名大 理学部1号館(多元数理科学研究科) 309室
- 時刻　：18:00〜19:30
- 参加者：12名
- 話題　：
-- hoge
-- foo
-- bar
- GQFpyOxgKcLvFU -- [[tgiqdjh]] &new{2008-09-23 (火) 10:36:14};

#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]
 (以下３行は前提とする関数)
 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小笠原)