[SOLVED] CS Tutorial 4 (4 Feb 2021) Topics Covered: Higher-order functions; code generation

Tutorial 4 (4 Feb 2021) Topics Covered: Higher-order functions; code generation
Guiding Questions
What makes up a higher-order function? What is the benefit of higher-order functions? What are curried forms of functions, and how does it relate to partial evaluation? How can we leverage partial evaluation with code generation?
Question 1
While we often work with only one list, needing to do something for each element of said list, some functions may want to work on pairs of elements, each coming from a separate list. This is related to the idea of Cartesian products of lists the Cartesian product of lists l1 and l2 is a list composed of tuples (e1, e2), for each e1 in l1 and each e2 in l2. Instead of first creating such a product list and then mapping a function on each element, implement the function
cross_map : (a -> b -> c) -> a list -> b list -> c list
which directly generates the mapped product list. The order should be [f l1_1 l2_1; f l1_2 l2_1; ; f l1_1 l2_2; ]
1. Make one implementation that uses a recursive inner helper.
2. Make one implementation that uses List HOFs.
Question 2
Using the following data type for trees,
type a bintree = X | Node of a bintree * a * a bintree
write a function
map (t : a bintree) : (a -> b) -> b bintree
which leverages code generation to map one tree onto another, conserving the tree structure while replacing all data inside with their mapped counterparts.

Extra question (not covered by tutorial)
Try to implement List.sort on your own! Match its intended signature:
sort : (a -> a -> int) -> a list -> a list
where the first argument is a comparison function. It returns a positive number if the first argument is larger (should be further to the right in the list), negative if the first argument is smaller (should be further to the left in the list), and 0 if both arguments are equal.