# 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.