### CSE 428: Solutions of exercises on Higher Order Programming

The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.

1. Define a function swapargs which takes a function f of type 'a * 'b -> 'c and returns a new function of type 'b * 'a -> 'c such that f(x,y) = swapargs(f)(y,x) for all x and y. (This is a one-liner.)
2. ### Solution

```   fun swapargs f = fn (y,x) => f(x,y);
```
or equivalently
```   fun swapargs f (y,x) = f(x,y);
```

3. Define the functions
1. ```   curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c
```
2. ```   uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c
```

curry takes a function f: 'a * 'b -> 'c and gives back the curried function g : 'a -> 'b -> 'c such that g x y = f(x,y). uncurry does the reverse, i.e. takes a function like g and returns a function like f.

4. ### Solution

• ```   fun curry f = fn x => fn y => f(x,y);
```
• ```   fun uncurry g = fn (x,y) => g x y;
```

5. Define a function nfold which takes two arguments, f and a non-negative integer n, and returns the n-fold composition of f. Namely, nfold(f,n)(x) = fn(x). Note that f0(x) = x.
6. ### Solution

```   fun nfold(f,n)(x) = if n<0 then 0  (* this case is not defined in the specification *)
else if n=0 then x
else f(nfold(f,n-1)(x));
```

7. Define a function fixedpoint which takes two arguments, a function f and an element x, and returns the smallest positive integer n such that fn(x) = x. Note that if the function has no fixedpoint, then this operation won't terminate. (I don't recommend using nfold for this, but you may.)
8. ### Solution

```   fun fixedpoint f x = let fun aux f x n v = if f v = x
then n
else aux f x (n+1) (f v)
in aux f x 1 x
end;
```

9. Define a function maximum which takes three arguments, a function f : int -> int and two integers a and b, and returns the integer y such that y = max{f(x) | a <= x <= b} (i.e. the greatest value of f in the interval [a,b]).
10. ### Solution

• Tail-recursive solution:
```   fun maximum f a b = let fun aux f x b y =  (* y is the maximum value of f so far, *)
if x > b       (* x is the current argument           *)
then y
else if (f x) > y
then aux f (x+1) b (f x)
else aux f (x+1) b y
in aux f (a+1) b (f a)
end;
```
• Non tail-recursive solution:
```   fun max x y = if x < y then y else x;

fun maximum f a b = if a = b then (f a)
else max (f a) (maximum f (a+1) b);
```

11. Define a function arg_maximum which takes three arguments, a function f : int -> int and two integers a and b, and returns the integer y such that f(y) = max{f(x) | a <= x <= b} (i.e. the argument y on which f takes the greatest value in the interval [a,b]).
12. ### Solution

• Tail-recursive solution: we use an extra argument in the definition of aux. v represents the maximum value of f so far, y the corresponding argument, and x the current argument.
```   fun arg_maximum f a b = let fun aux f x b y v =
if x > b
then y
else if (f x) > v
then aux f (x+1) b x (f x)
else aux f (x+1) b y v
in aux f (a+1) b a (f a)
end;
```
• Non tail-recursive solution:
```   fun arg_maximum f a b = if a = b then a
else let val y = arg_maximum f (a+1) b
in if (f a) < (f y) then y else a
end;
```

13. Define a polymorphic function quicksort : ('a list) -> ('a * 'a -> bool) -> ('a list) such that, given a list l and a comparison predicate p, quicksort l p returns a list with the same elements as l, ordered w.r.t. to the relation p. For instance:
```   quicksort [2,1,3] (op <) = [1,2,3]
quicksort [2,1,3] (op >) = [3,2,1]
quicksort [~2,3,1] (fn(x,y) => x*x < y*y) = [1,~2,3]
quicksort [[1,2],[4],[]] (fn(l,k) => length l < length k) = [[],[4],[1,2]]
```
(Remember that op transforms an infix operator into the corresponding prefix operator.) In practice, the required function should be defined as a generalization of the ordinary quicksort function, using the generic test p(x,y) instead of x < y.
14. ### Solution

```   fun split x [] p = ([],[])
| split x (y::l) p = let val (k1,k2) = split x l p
in if p(x,y) then (k1,y::k2) else (y::k1,k2)
end;

fun quicksort [] p = []
| quicksort (x::l) p = let val (k1,k2) = split x l p
in (quicksort k1 p) @ (x::(quicksort k2 p))
end;
```

15. Consider the following datatype declaration for bynary trees:
```   datatype 'a btree = emptybt | consbt of ('a * 'a btree * 'a btree);
```
Define in ML a function maptree : ('a -> 'b) -> 'a btree -> 'b btree which, given a function f : 'a -> 'b, and a binary tree t : 'a btree, gives as result the tree obtained from t by replacing each node n by f(n).
16. ### Solution

```   fun maptree f emptybt = emptybt
| maptree f (consbt(x,t1,t2)) = consbt(f x, maptree f t1, maptree f t2);
```

17. Consider the function reduce: ('a * 'b -> 'b) -> 'b -> 'a list -> 'b defined as
```   fun reduce f v [] = v
| reduce f v (x::l) = f(x, reduce f v l);
```
Using reduce, define the functions
1. exists 'a list -> ('a -> bool) -> bool such that exists l p holds if and only if in the list l there is at least an element which satisfy the property p.
2. forall 'a list -> ('a -> bool) -> bool such that forall l p holds if and only if every element of the list l satisfies the property p.
The definitions should have the form
```   fun exists l p = reduce ...;
fun forall l p = reduce ...;
```
18. ### Solution

1. ```   fun exists l p = reduce (fn(x,y) => if (p x) then true else y) false l;
```
2. ```   fun forall l p = reduce (fn(x,y) => if (p x) then y else false) true l;
```

19. Primitive recursion over the natural numbers is a subset of recursive functions which have a simple, but natural structure. The general form of a primitive recursive function p is
```   fun p 0 = v
|   p n = f(p(n-1),n)
```
where f is the appropriate function which computes the value for the recursive case. For example, the function sum_up_to (which sums up the first n natural numbers) has this form in which v = 0 and f = op + (or f = fn(x,y)=>x+y).

We can define a function iter which, given a function f and value v, returns the primitive recursive function using these functions:

```   fun iter(f,v) 0 = v
| iter(f,v) n = f(iter(f,v) (n-1), n);
```
We can define primitive recursive function using this function. For example, the function sum_up_to can be defined as follows
```   val sum_up_to = iter(op +,0);
```
1. Use iter to define the following primitive recursive functions:
1. fact, defined by fact(n) = n! (the factorial of n).
2. power_2, defined by power_2(n) = 2n
2. The definition of iter only supports defining functions of type int -> 'a. Many other primitive recursive functions take additional arguments. For our purposes, we can assume just one additional argument since we can always bundle up multiple arguments into a single pair. This more-generalized form can be written as
```   fun p (0,a) = g(a)
| p (n,a) = f(p(n-1,h(n,a)), n, a);
```
Note that the function f now takes a as an argument. The function g is used to compute the value at the base case, and the function h is used to compute the second argument to the recursive call.
1. Define a generalized version, gen_iter, which takes three functions f, g and h, and produces a primitive recursive function of type (int * 'a) -> 'b. As an example use of gen_iter, we can define the tail-recursive version of factorial as:
```   val tfact = gen_iter(fn (x,y,z)=>x, fn x=>x, fn(x,y)=>x*y);
```
2. Use gen_iter to define the primitive recursive function power, where power(n,m) = mn.
20. ### Solution

1. ```   val fact = iter(op *,1);
```
2. ```   val power_2 = iter(fn(x,y)=>x*2, 1);
```
1. ```   fun gen_iter(f,g,h) (0,a) = g(a)
| gen_iter(f,g,h) (n,a) = f(gen_iter(f,g,h)(n-1,h(n,a)),n,a);
```
2. ```   val power = gen_iter(fn(x,y,z)=>x*z, fn x=>1, fn(x,y)=>y);
```