Difference between revisions of "Binary Int Tree Assignment"
Jump to navigation
Jump to search
| (7 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
Prepare for the [[Binary_Search_Tree_Assignment|Binary Search Tree]] Exercise with a simpler warm up. | Prepare for the [[Binary_Search_Tree_Assignment|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== | ||
| + | [[File:Binary int tree 1.svg]] | ||
| + | ==3== | ||
| + | NODE(NODE(EMPTY, 1, EMPTY), 2, NODE(EMPTY, 3, EMPTY))) | ||
| − | == | + | [[File:Binary int tree 3.svg]] |
| − | + | ==7== | |
| + | NODE(NODE(NODE(EMPTY, 1, EMPTY), 2, NODE(EMPTY, 3, EMPTY)), 4, NODE(NODE(EMPTY, 5, EMPTY), 6, NODE(EMPTY, 7, EMPTY)))) | ||
| − | + | [[File:Binary int tree 7.svg]] | |
| − | [[File: | + | |
| − | + | =Code to Implement= | |
| + | {{SMLToImplement|binary_int_tree|sum<br/>sum_accumulate<br/>fold_rnl|warmup_binary_int_tree}} | ||
==sum== | ==sum== | ||
| + | Traverse the tree and produce the sum. | ||
| + | |||
<nowiki>fun sum(node : int_tree) : int = | <nowiki>fun sum(node : int_tree) : int = | ||
raise Fail("NotYetImplemented")</nowiki> | raise Fail("NotYetImplemented")</nowiki> | ||
==sum_accumulate== | ==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. | ||
| + | |||
<nowiki>fun sum_accumulate(init : int, node : int_tree) : int = | <nowiki>fun sum_accumulate(init : int, node : int_tree) : int = | ||
raise Fail("NotYetImplemented")</nowiki> | raise Fail("NotYetImplemented")</nowiki> | ||
==fold_rnl== | ==fold_rnl== | ||
| − | [https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in- | + | Fold the tree with a [https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order,_RNL reverse order traversal] invoking <code>f</code> with each element and the accumulated value, using the evaluation as the updated accumulated value. |
| + | |||
<nowiki>(* | <nowiki>(* | ||
* depth-first, reverse in-order traversal | * depth-first, reverse in-order traversal | ||
| − | * https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in- | + | * https://en.wikipedia.org/wiki/Tree_traversal#Reverse_in-order,_RNL |
*) | *) | ||
fun fold_rnl(f : (int * 'a) -> 'a, init : 'a, node : int_tree) : 'a = | fun fold_rnl(f : (int * 'a) -> 'a, init : 'a, node : int_tree) : 'a = | ||
Latest revision as of 04:14, 21 October 2022
Contents
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.
