Difference between revisions of "Binary Search Tree Assignment"
Jump to navigation
Jump to search
| Line 12: | Line 12: | ||
==BinaryTree== | ==BinaryTree== | ||
datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree | datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree | ||
| − | ===insert=== | + | ===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=== | + | ====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 | ||
| − | ===find=== | + | |
| + | ===higher order functions=== | ||
| + | ====find==== | ||
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.find:VAL List.find] | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.find:VAL List.find] | ||
| + | |||
fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option = | fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option = | ||
raise NotYetImplemented | raise NotYetImplemented | ||
| + | |||
| + | ====find_order_hof==== | ||
| + | fun find_order_hof (order:traversal_order) (predicate:'a->bool) (t:'a tree) : 'a option = | ||
| + | raise NotYetImplemented | ||
| + | |||
===map=== | ===map=== | ||
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.map:VAL List.map] | reference: [http://sml-family.org/Basis/list.html#SIG:LIST.map:VAL List.map] | ||
Revision as of 03:34, 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 Implement
- binary_tree/binary_tree.sml
- binary_tree/apps_using_binary_tree.sml
BinaryTree
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
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
