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.

The superscript "(s)" stands for "solution provided". You can find the solution of these exercises here.

^{(s)}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.)^{(s)}Define the functionscurry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c

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.`^{(s)}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`^{n}`(x)`. Note that`f`^{0}`(x) = x`.^{(s)}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`^{n}`(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.)^{(s)}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]`).^{(s)}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]`).^{(s)}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`.^{(s)}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)`.^{(s)}Consider the function`reduce: ('a * 'b -> 'b) -> 'b -> 'a list -> 'b`defined asfun reduce f v [] = v | reduce f v (x::l) = f(x, reduce f v l);

Using`reduce`, define the functions`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`.`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`.

fun exists l p = reduce ...; fun forall l p = reduce ...;

^{(s)}*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`isfun 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 n`can be defined as followsval sum_up_to = iter(op +,0);

- Use
`iter`to define the following primitive recursive functions:`fact`, defined by`fact(n) = n!`(the factorial of`n`).`power_2`, defined by`power_2(n) = 2`^{n}

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

- Use
`gen_iter`to define the primitive recursive function`power`, where`power(n,m) = m`^{n}.

- Define a generalized version,

- Use