第5章からExerciseが増えてる。このエントリではExercise 3-6だけ。
なんかリストの章なのにリスト操作関数ほとんど使わないで解いてる。これは大量のツッコミを受けそうだ。。。
Exercise 3-6 a,b
問題
Exercise 3-6 リストを集合とみなして,以下の集合演算をする関数を定義せよ.
a. belong a s で a が s の要素かどうかを判定する関数 belong.
b. intersect s1 s2 で s1 と s2 の共通部分を返す関数 intersect.
但し,集合なので,要素は重複して現れてはならないことに気をつけよ. (関数の引数には重複してないものが与えられるという仮定を置いてもよい.)
自分の答え
(* Exercise 3-6-a*) let rec belong a = function | [] -> false | (x::xs) -> if a=x then true else (belong a xs) ;; (* Exercise 3-6-b*) let intersect s1 s2 = let rec intersect s1 s2 set = match (s1, s2) with | ([], _) | (_ ,[]) -> set | (x1::xs1, x2::xs2) -> if x1=x2 then (intersect xs1 xs2 (x1::set)) else (intersect xs1 xs2 set) in intersect s1 s2 [] ;;
Exercise 3-6 c,d
問題
Exercise 3-6 リストを集合とみなして,以下の集合演算をする関数を定義せよ.
c. union s1 s2 で s1 と s2 の和を返す関数 union.
d. diff s1 s2 で s1 と s2 の差を返す関数 diff
但し,集合なので,要素は重複して現れてはならないことに気をつけよ. (関数の引数には重複してないものが与えられるという仮定を置いてもよい.)
自分の答え
(* Exercise 3-6-c *) let set l = let rec set s = function | [] -> s | (x::xs) -> if belong x s then set s xs else set (x::s) xs in set [] l ;; let union s1 s2 = let rec union s1 s2 t u = match (s1, s2) with | ([], []) -> u | ([], s) -> s @ u | (x1::xs1, []) -> union xs1 t [] (x1::u) | (x1::xs1, x2::xs2) -> if x1=x2 then union xs1 (xs2 @ t) [] (x1::u) else union (x1::xs1) xs2 (x2::t) u in let l1 = set s1 and l2 = set s2 in union l1 l2 [] [] ;; Printf.printf "\n%s" "union ->";; print_list (union [8;1;1;2;3;4;5;3] [2;2;4;4;6;7;7;5;5;9]);; Printf.printf "\n";; (* Exercise 3-6-d *) let diff s1 s2 = let rec diff s1 s2 t d = match (s1, s2) with | ([], _) -> d | (x1::xs1, []) -> diff xs1 t [] (x1::d) | (x1::xs1, x2::xs2) -> if x1=x2 then diff xs1 xs2 [] d else diff (x1::xs1) xs2 (x2::t) d in let l1 = set s1 and l2 = set s2 in diff l1 l2 [] [] ;; Printf.printf "\n%s" "diff ->";; print_list (diff [8;1;1;2;3;4;5;3] [2;2;4;4;6;7;7;5;5;9]);; Printf.printf "\n";;