Binary Int Tree Assignment

Motivation

Prepare for the Binary Search Tree Exercise with a simpler warm up.

int_tree

 datatype int_tree = NODE of (int_tree * int * int_tree) | EMPTY

Examples

EMPTY

EMPTY

1

3

NODE(NODE(EMPTY, 1, EMPTY), 2, NODE(EMPTY, 3, EMPTY)))

7

NODE(NODE(NODE(EMPTY, 1, EMPTY), 2, NODE(EMPTY, 3, EMPTY)), 4, NODE(NODE(EMPTY, 5, EMPTY), 6, NODE(EMPTY, 7, EMPTY))))

Code to Implement

file:	src/main/sml/warmup_binary_int_tree/binary_int_tree.sml
functions:	sum sum_accumulate fold_rnl

sum

Traverse the tree and produce the sum.

fun sum(node : int_tree) : int =
	raise Fail("NotYetImplemented")

sum_accumulate

Traverse the tree and produce the sum, but this time perform the operation in a more fold like manner with an accumulated value.

fun sum_accumulate(init : int, node : int_tree) : int = 
	raise Fail("NotYetImplemented")

fold_rnl

Fold the tree with a reverse order traversal invoking f with each element and the accumulated value, using the evaluation as the updated accumulated value.

(*
 * depth-first, reverse in-order traversal
 * https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order,_RNL
 *)
fun fold_rnl(f : (int * 'a) -> 'a, init : 'a, node : int_tree) : 'a = 
	raise Fail("NotYetImplemented")

Testing

source folder:	src/test/sml/warmup_binary_int_tree
how to run with CM.make verbosity off:	sml -Ccm.verbose=false run_binary_int_tree_testing.sml
how to run with CM.make verbosity on:	sml run_binary_int_tree_testing.sml

note: ensure that you have removed all printing to receive credit for any assignment.

SML Error Messages