binary_search_tree.sml

datatype 'a Btree = Empty | Node of 'a * 'a Btree * 'a Btree;

fun member(x: 'a, ordering_relation: 'a * 'a -> bool, equality_relation: 'a * 'a -> bool, Empty) = false
	| member(x: 'a, ordering_relation: 'a * 'a -> bool, equality_relation: 'a * 'a -> bool, Node(y, left, right)) =
		if equality_relation(x,y) then true
		else
			if ordering_relation(x,y) then member(x, ordering_relation, equality_relation, left)
			else member(x, ordering_relation, equality_relation, right);
  		
fun insert(x, ordering_relation: 'a * 'a -> bool, equality_relation: 'a * 'a -> bool, Empty) = Node(x, Empty, Empty)
	| insert(x, ordering_relation: 'a * 'a -> bool, equality_relation: 'a * 'a -> bool, Node(y, left, right)) =
		if equality_relation(x,y) then Node(y, left, right)
		else
			if ordering_relation(x,y) then Node(y, insert(x, ordering_relation, equality_relation, left), right)
      else Node(y, left, insert (x, ordering_relation, equality_relation, right));

fun printtree(Empty, print_function: 'a -> unit ) = print ""
	| printtree(Node(x, left, right), print_function: 'a -> unit) = printtree(left, print_function) ^ print_function(x) ^ printtree(right, print_function);