Difference between revisions of "Binary Search Tree Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
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
  
===map===
+
===fold_order_hof===
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.map:VAL List.map]
+
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.foldl:VAL List.foldl]
  fun map(f : 'a -> 'b, t : 'a tree) : 'b tree =  
+
  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, t : 'a tree) : 'a tree =  
+
  fun filter (predicate : 'a -> bool) (t : 'a tree) : 'a tree =  
 
     raise NotYetImplemented
 
     raise NotYetImplemented
  
===find_lnr===
+
===filter_civil_war_style===
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.find:VAL List.find]
+
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
  
reference: [https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR) In-order traversal]
+
===map_to_tree_hof (Optional)===
fun find_lnr(predicate : 'a -> bool, t : 'a tree) : 'a option =
+
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
  
===fold_lnr===
+
fun map_to_tree_lnr compare_function f t =  
reference: [http://sml-family.org/Basis/list.html#SIG:LIST.foldl:VAL List.foldl]
+
    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
  
reference: [https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR) In-order traversal]
+
===map_to_list_hof (Optional)===
 +
fun map_to_list_hof (order:traversal_order) (f : 'a -> 'b) (t : 'a tree) : 'b list =
 +
    raise NotYetImplemented
  
  fun fold_lnr(f : 'a * 'b -> 'b, init : 'b, t : 'a tree ) : 'b =  
+
  fun map_to_list_lnr f t =  
    raise NotYetImplemented
+
    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

LNR would produce: ABCDEFGHI
RNL would produce: IHGFEDCBA

In-order LNR

Reverse in-order RNL

 datatype traversal_order = LNR | RNL

BinaryTree

file: src/main/sml/binary_tree/binary_tree.sml Smlnj-logo.png
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 Smlnj-logo.png
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