Difference between revisions of "Binary Search Tree Assignment"
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
[[File:Sorted binary tree inorder.svg|Sorted binary tree inorder]] | [[File:Sorted binary tree inorder.svg|Sorted binary tree inorder]] | ||
| − | =Code | + | |
| − | + | =Code to Investigate= | |
| − | + | ==order== | |
| + | [http://sml-family.org/Basis/general.html#SIG:GENERAL.order:TY 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 [http://sml-family.org/Basis/list.html list] provides on our binary tree. | ||
| + | |||
| + | =BinaryTree= | ||
| + | source file: binary_tree/binary_tree.sml | ||
| − | |||
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree | datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree | ||
| − | + | ==core== | |
| − | + | ===insert=== | |
fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree = | fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree = | ||
raise NotYetImplemented | raise NotYetImplemented | ||
| − | + | ===remove=== | |
fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree = | fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree = | ||
raise NotYetImplemented | raise NotYetImplemented | ||
| Line 56: | Line 63: | ||
raise NotYetImplemented | raise NotYetImplemented | ||
| − | + | =Application= | |
| − | + | source file: binary_tree/apps_using_binary_tree.sml | |
| + | ==max_height== | ||
fun max_height(t : 'a BinaryTree.tree) : int = | fun max_height(t : 'a BinaryTree.tree) : int = | ||
raise NotYetImplemented | raise NotYetImplemented | ||
| − | + | ==sum_int_tree== | |
fun sum_int_tree(t : int BinaryTree.tree) : int = | fun sum_int_tree(t : int BinaryTree.tree) : int = | ||
raise NotYetImplemented | raise NotYetImplemented | ||
Revision as of 03:39, 22 February 2020
We will build some of the Higher Order Function Hall of Fame inductees but for a tree datatype.
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree
Contents
Code to Investigate
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.
BinaryTree
source file: binary_tree/binary_tree.sml
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree
core
insert
fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree =
raise NotYetImplemented
remove
fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree =
raise NotYetImplemented
higher order functions
find
reference: List.find
fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option =
raise NotYetImplemented
find_order_hof
fun find_order_hof (order:traversal_order) (predicate:'a->bool) (t:'a tree) : 'a option =
raise NotYetImplemented
map
reference: List.map
fun map(f : 'a -> 'b, t : 'a tree) : 'b tree =
raise NotYetImplemented
filter
reference: List.filter
fun filter(predicate : 'a -> bool, t : 'a tree) : 'a tree =
raise NotYetImplemented
find_lnr
reference: List.find
reference: In-order traversal
fun find_lnr(predicate : 'a -> bool, t : 'a tree) : 'a option =
raise NotYetImplemented
fold_lnr
reference: List.foldl
reference: In-order traversal
fun fold_lnr(f : 'a * 'b -> 'b, init : 'b, t : 'a tree ) : 'b =
raise NotYetImplemented
Application
source file: binary_tree/apps_using_binary_tree.sml
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
studioTree/unittest_tree.sml
