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

Solution

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

or equivalently

   fun swapargs f (y,x) = f(x,y);

---

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

Solution

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

   fun uncurry g = fn (x,y) => g x y;

---

3. 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) = fⁿ(x). Note that f⁰(x) = x.

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

---

4. Define a function fixedpoint which takes two arguments, a function f and an element x, and returns the smallest positive integer n such that fⁿ(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.)

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;

---

5. 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]).

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

---

6. 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]).

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;
  

---

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

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;

---

8. 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).

Solution

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

---

9. 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 ...;
   

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;
   

---

10. 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) = 2ⁿ
    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) = mⁿ.

Solution

1. 1.    val fact = iter(op *,1);
         

   2.    val power_2 = iter(fn(x,y)=>x*2, 1);
         

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