Difference between revisions of "Binary Search Tree Assignment"
Jump to navigation
Jump to search
(→fun) |
|||
Line 44: | Line 44: | ||
===find_order_hof=== | ===find_order_hof=== | ||
+ | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.find:VAL List.find] | ||
fun find_order_hof (order:traversal_order) (predicate:'a->bool) (t:'a tree) : 'a option = | fun find_order_hof (order:traversal_order) (predicate:'a->bool) (t:'a tree) : 'a option = | ||
raise NotYetImplemented | raise NotYetImplemented | ||
Line 52: | Line 53: | ||
find_order_hof RNL predicate t | find_order_hof RNL predicate t | ||
− | === | + | ===fold_order_hof=== |
− | reference: [http://sml-family.org/Basis/list.html#SIG:LIST. | + | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.foldl:VAL List.foldl] |
− | fun | + | fun fold_order_hof (order:traversal_order) (f : 'a * 'b -> 'b) (init : 'b) (t : 'a tree) : 'b = |
raise NotYetImplemented | raise NotYetImplemented | ||
− | ===filter=== | + | 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 (Optional)=== | ||
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.filter:VAL List.filter] | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.filter:VAL List.filter] | ||
− | fun filter(predicate : 'a -> bool | + | fun filter (predicate : 'a -> bool) (t : 'a tree) : 'a tree = |
raise NotYetImplemented | raise NotYetImplemented | ||
− | === | + | ===filter_civil_war_style=== |
− | reference: [http://sml-family.org/Basis/list.html#SIG:LIST. | + | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.filter:VAL List.filter] |
+ | fun filter_civil_war_style (predicate : 'a -> bool) (t : 'a tree) : 'a tree = | ||
+ | raise NotYetImplemented | ||
+ | ===map_to_tree_of_questionable_validity=== | ||
+ | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.map:VAL List.map] | ||
+ | fun map_to_tree_of_questionable_validity (f : 'a -> 'b) (t : 'a tree) : 'b tree = | ||
+ | raise NotYetImplemented | ||
− | + | ===map_to_tree_hof (Optional)=== | |
− | + | fun map_to_tree_hof (order:traversal_order) (compare_function:(('b * 'b) -> order)) (f : 'a -> 'b) (t : 'a tree) : 'b tree = | |
raise NotYetImplemented | 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 (Optional)=== | |
+ | fun map_to_list_hof (order:traversal_order) (f : 'a -> 'b) (t : 'a tree) : 'b list = | ||
+ | raise NotYetImplemented | ||
− | fun | + | 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= | =Applications= |
Revision as of 04:51, 22 February 2020
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
fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree = raise NotYetImplemented
find
reference: List.find
fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option = raise NotYetImplemented
fun
to_first_and_last
fun to_first_and_last(order:traversal_order, left:'a tree, right:'a tree) = raise NotYetImplemented
find_order_hof
reference: List.find
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
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 (Optional)
reference: List.filter
fun filter (predicate : 'a -> bool) (t : 'a tree) : 'a tree = raise NotYetImplemented
filter_civil_war_style
reference: List.filter
fun filter_civil_war_style (predicate : 'a -> bool) (t : 'a tree) : 'a tree = raise NotYetImplemented
map_to_tree_of_questionable_validity
reference: List.map
fun map_to_tree_of_questionable_validity (f : 'a -> 'b) (t : 'a tree) : 'b tree = raise NotYetImplemented
map_to_tree_hof (Optional)
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 (Optional)
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