Binary Search Tree Assignment
We will implement a binary search tree data structure as well as a few Higher Order Function Hall of Fame inductees.
Background
order
SML's General structure's order
datatype order = LESS | EQUAL | GREATER
Values of type order are used when comparing elements of a type that has a linear ordering.
list
We will implement some of the higher ordered functions list provides on our binary tree.
traversal order
datatype traversal_order = LNR | RNL
BinaryTree
file: | src/main/sml/binary_tree/binary_tree.sml | ![]() |
functions: | insert remove find ... |
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree
core
insert
note: this function is curried.
fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree = raise NotYetImplemented
remove
note: this function is curried.
fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree = raise NotYetImplemented
find
reference: List.find
note: this function is curried.
fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option = raise NotYetImplemented
fun
to_first_and_last
This function is useful for find_order_hof and fold_order_hof.
It simply returns the left and right tree as a 2-tuple in the appropriate order based on the specified traversal_order.
fun to_first_and_last(order:traversal_order, left:'a tree, right:'a tree) = raise NotYetImplemented
find_order_hof
reference: List.find
Instead of a binary search style find, here we create a find based on a traversal order and a predicate. It returns the first item node value it encounters which passes the predicate function.
note: this function is curried.
fun find_order_hof (order:traversal_order) (predicate:'a->bool) (t:'a tree) : 'a option = raise NotYetImplemented
fun find_lnr (predicate:'a->bool) (t:'a tree) : 'a option = find_order_hof LNR predicate t fun find_rnl (predicate:'a->bool) (t:'a tree) : 'a option = find_order_hof RNL predicate t
fold_order_hof
reference: List.foldl
note: this function is curried.
fun fold_order_hof (order:traversal_order) (f : 'a * 'b -> 'b) (init : 'b) (t : 'a tree) : 'b = raise NotYetImplemented
fun fold_lnr f init t = fold_order_hof LNR f init t fun fold_rnl f init t = fold_order_hof RNL f init t
filter (Not Required)
reference: List.filter
note: this function is curried.
fun filter (predicate : 'a -> bool) (t : 'a tree) : 'a tree = raise NotYetImplemented
filter_civil_war_style
This function is much like filter, only instead of deftly omitting the nodes which do not pass the predicate, it lops off the entire subtree of those nodes which do not pass the predicate.
note: this function is curried.
fun filter_civil_war_style (predicate : 'a -> bool) (t : 'a tree) : 'a tree = raise NotYetImplemented
map_to_tree_of_questionable_validity
reference: List.map note: this function is curried.
fun map_to_tree_of_questionable_validity (f : 'a -> 'b) (t : 'a tree) : 'b tree = raise NotYetImplemented
map_to_tree_hof (Not Required)
note: this function is curried.
fun map_to_tree_hof (order:traversal_order) (compare_function:(('b * 'b) -> order)) (f : 'a -> 'b) (t : 'a tree) : 'b tree = raise NotYetImplemented
fun map_to_tree_lnr compare_function f t = map_to_tree_hof LNR compare_function f t fun map_to_tree_rnl compare_function f t = map_to_tree_hof RNL compare_function f t
map_to_list_hof (Not Required)
note: this function is curried.
fun map_to_list_hof (order:traversal_order) (f : 'a -> 'b) (t : 'a tree) : 'b list = raise NotYetImplemented
fun map_to_list_lnr f t = map_to_list_hof LNR f t fun map_to_list_rnl f t = map_to_list_hof RNL f t
Applications
file: | src/main/sml/binary_tree/apps_using_binary_tree.sml | ![]() |
functions: | max_height sum_int_tree |
max_height
fun max_height(t : 'a BinaryTree.tree) : int = raise NotYetImplemented
sum_int_tree
fun sum_int_tree(t : int BinaryTree.tree) : int = raise NotYetImplemented
Testing
file: | unit_test_binary_tree_and_apps.sml | |
source folder: | src/test/sml/binary_tree |
Pledge, Acknowledgments, Citations
file: | studio-binary-tree-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge