Objective Caml 入門 手習い（5章） その2

第5章からExerciseが増えてる。このエントリではExercise 3-6だけ。

• Objective Caml 入門

なんかリストの章なのにリスト操作関数ほとんど使わないで解いてる。これは大量のツッコミを受けそうだ。。。

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";;