EoPL - Ch 1 - Ex 17

Exercise 17 in Chapter 1 of Essentials of Programming Languages furthers the aims of Exercise 15 and Exercise 16. The subparts of Exercise 17 are more algorithmic in nature than the previous exercises, however. Namely, they touch upon sorting and binary tree traversal.

Ex. 17, Pt. 1
Define a function path : (n : int) * (bst : BinarySearchTree) -> [left|right] that returns a list, where each element is either left or right, that describes the path to the node in bst which contains n. If that node is the root node, return an empty list. Solution.

Ex. 17, Pt. 2
Define a function sort : (lon : [int]) -> [int] that returns a list like lon but with all elements sorted in increasing order. Solution.

Ex. 17, Pt. 3
Define a function sort : (predicate : int * int -> bool) * (lon : [int]) -> [int] that returns a list like lon but with all elements sorted according to the comparison predicate. Solution.