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

  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

  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

  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

  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)
       fun quicksort [] p = []
         | quicksort (x::l) p = let val (k1,k2) = split x l p
                                 in (quicksort k1 p) @ (x::(quicksort k2 p))

  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);