- (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 functions
curry : ('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) = fn(x).
Note that f0(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 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.)
- (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 as
fun 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.
The definitions should have the form
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 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 n can be defined as follows
val 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) = 2n
- 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.
- 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) = mn.