##master-page:NoteTemplate
#format wiki
#language ja
= 第3回 =

== 課題4 ==

平均（最悪でない）時間計算量がO(log n)であればいいので、例えば二分木を作ればいいはず。

二分木を作る場合、特に大変なのはremoveでしょうか。

{{{#!highlight ocaml
module MyMultiset2 = functor (Elem : ORDERED_TYPE) -> struct
	exception Error_btree
	type t = Node of Elem.t * t * t | Leaf

	(* 中略 *)

	(* 木の最小要素を返す *)
	let rec search_min set =
		match set with
			| Leaf -> raise Error_btree
			| Node (x, Leaf, _) -> x
			| Node (_, left, _) -> search_min left

	(* 木の最小要素を消す *)
	let rec delete_min set = 
		match set with
			| Node (v, Leaf, right) -> right
			| Node (v, left, right) -> Node (v, (delete_min left), right)
			| Leaf -> raise Error_btree

	(* 要素の削除 *)
	let rec remove elem set =
		match set with
		  	| Leaf -> Leaf
			| Node (v, left, right) when eq v elem -> 
				if (right = Leaf) then left
				else if (left = Leaf) then right
				else 
					let min = search_min right in
					Node (min, left, delete_min right)
			| Node (v, left, right) ->
				if (grt elem v) then Node (v, left, remove elem right)
				else Node (v, remove elem left, right)


	(* 中略 *)
end
}}}

== 課題5 ==

定義は自分で決めていいらしいので、「1000回addやremoveを繰り返しても、２つの実装の実行結果が変わらないこと」とか適当に定義すればいい思う。

真面目な解き方は誰かが加筆してくれることでしょう(ﾁﾗｯ

== 課題7 ==

let recを使って

{{{#!highlight ocaml
let rec map f = function
        | Leaf -> Leaf
        | Node (v, next) -> Node (f v, map (map f) next);;
}}}

とすると、「Error: This expression has type 'a t -> 'b t but an expression was expected of type 'a -> 'b」と型エラーがでます。
そこでmodule recを駆使して書いてみると、

{{{#!highlight ocaml
module rec Tree :
sig val map : ('a -> 'b) -> ('a t -> 'b t) end =
struct
	let map f = function
		| Leaf -> Leaf
		| Node (v, next) -> Node(f v, Tree.map (Tree.map f) next);;
end;;
}}}

うまくいきます。詳しい解説はis2009のwikiに書かれています。

== 課題8 ==

('a, 'b) equalは同値関係（=とか<=>）に対応する型だと思われます。（reflは反射律、symmは対称律、transは推移律に対応）

同値関係は「（AならばB）かつ（BならばA）」という命題と同じ（？）と考えられるので、('a, 'b) equalは、例えば

{{{#!highlight ocaml
type ('a, 'b) equal = ('a -> 'b) * ('b -> 'a)
}}}

と定義すればいいと思います。

== 課題9 ==

よく分かりません（

valueやexprの引数に('a, 'b) equalを持たせる理由が謎です。

なんとなく型キャストができるようにしなさいと言っているような気がしますが気のせいかもしれません。

だれか分かる人は加筆してください。

----
[[Categoryノート]]