(-- CSE505 Homework 4 Sample Solutions --)


-- Question 1

	-- the Tree object
abstract object Tree;

	-- the Node
template object Node isa Tree;
	var field left(n@Node);
	var field right(n@Node);
	var field element(n@Node);

	-- the leaves of the Tree
concrete object Empty isa Tree;

	-- a constructor or two
method new_node(value)
{
	object isa Node { left := Empty, right := Empty, element := value };
}

method new_node(l, r, value)
{
	object isa Node { left := l, right := r, element := value };
}

	-- constructing an empty tree
let var emptyTree := Empty;

	-- constructing a single node tree
let var unitTree := new_node(5);

	-- constructing a slightly more complex tree
let var complexTree := new_node(Empty, unitTree, 2);




-- Question 2

	-- here's a nice (but maybe inefficient) functional version that
	-- returns a new tree with the value added
method insert(n@Node, val)
{
	if (val = n.element,
	{
		^n;
	});
	if (val < n.element,
	{
		new_node(insert(n.left, val), n.right, n.element);
	},
	-- else
	{
		new_node(n.left, insert(n.right, val), n.element);
	});
}

	-- inserting into empty tree returns a new node
method insert(n@Empty, val)
{
	new_node(val);
}

	-- nothing is the member of the empty tree
method member(n@Empty, val) { false }

	-- test the element for a membership, then test appropriate subtree
	-- assumes the tree is ordered
method member(n@Node, val)
{
	if (val = n.element, { ^true });

	if (val < n.element,
	{
		member(n.left, val);
	},
	-- else
	{
		member(n.right, val);
	});
}

	-- membership test: returns false
member(complexTree, 3);

	-- insertion and membership test: returns true
member(insert(complexTree, 3), 3);

	-- insertion test: returns tree{4} if print_string is defined as below
insert(Empty, 4);




-- Question 3

	-- do nothing for the empty tree
method do(n@Empty, closure)
{
}

	-- for a node, evaluate the closure on the element and then
	-- recursively call do for the left and right subtrees
method do(n@Node, closure)
{
	eval(closure, n.element);
	do(n.left, closure);
	do(n.right, closure);
}

	-- the print_string method, for convenience
method print_string(tree@Tree) {
	let var s := "tree{";
	let var first := true;
	tree.do(&(elem){
		if(first, {
			first := false;
		}, {
			s := s || ",";
		});
		s := s || elem.print_string;
	});
	s || "}"
}




-- Question 4

	-- sum_tree uses a closure to add each element to a sum variable
method sum_tree(tree@Tree)
{
	let var sum := 0;
	tree.do( &(element) { sum := sum + element; });
	sum
}

	-- testing: returns 7
sum_tree(complexTree);




-- Question 5

	-- reducing the empty tree results in the unit element
method reduce_tree(tree@Empty, operator, unit) { unit }

	-- reducing a node means reducing its children then applying the
	-- unit element to the result
method reduce_tree(tree@Node, operator, unit)
{
	eval(operator,
		eval(operator,
			reduce_tree(tree.left, operator, unit),
			tree.element),
		reduce_tree(tree.right, operator, unit))
}

	-- sum_tree implemented with reduce_tree
method reduce_sum_tree(tree@Node)
{
	reduce_tree(tree, &(a, b) { a + b }, 0)
}

	-- a test, returns 7
reduce_sum_tree(complexTree);




-- Question 6, part a

	-- the Singleton object
template object Singleton isa Tree;
	var field element(s@Singleton);

	-- Singleton constructor
method new_singleton(value) {
	object isa Singleton { element := value }
}

	-- insert for Singletons.  Creates a new Node with this Singleton as
	-- a child
method insert(s@Singleton, value)
{
	if (s.element = value,
	{
		^s;
	});
	if (s.element < value,
	{
		new_node(s, Empty, value)
	},
	-- else
	{
		new_node(Empty, s, value)
	});
}

	-- member for Singletons
method member(s@Singleton, value)
{
	s.element = value
}

	-- do for Singletons
method do(s@Singleton, closure)
{
	eval(closure, s.element)
}



-- Question 6, part b
--
-- It is not possible to do this kind of extension without modification
-- in ML because the ML
-- datatype definition requires that all cases for the datatype be defined
-- in one datatype definition.  Also, the different cases for each function
-- must be defined in one place; thus you must be able to change all the
-- source files in order to extend a datatype.
--
-- The extension itself doesn't require modifying any existing clauses in
-- the datatype definition or function definitions, it just requires adding
-- cases to all function definitions and datatype definitions.  One could
-- imagine a version of ML that allows you to declare different cases of a
-- function separately (typing in this version of ML would be trickier since
-- a function's type comes from multiple places) and in this version this kind
-- of extension could be done without modifying code.

        -- for testing out expressions
breakpoint();