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.
fun swapargs f = fn (y,x) => f(x,y);or equivalently
fun swapargs f (y,x) = f(x,y);
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.
fun curry f = fn x => fn y => f(x,y);
fun uncurry g = fn (x,y) => g x y;
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));
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;
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;
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);
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;
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;
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.
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;
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).
fun maptree f emptybt = emptybt | maptree f (consbt(x,t1,t2)) = consbt(f x, maptree f t1, maptree f t2);
fun reduce f v [] = v | reduce f v (x::l) = f(x, reduce f v l);Using reduce, define the functions
fun exists l p = reduce ...; fun forall l p = reduce ...;
fun exists l p = reduce (fn(x,y) => if (p x) then true else y) false l;
fun forall l p = reduce (fn(x,y) => if (p x) then y else false) true l;
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);
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.
val tfact = gen_iter(fn (x,y,z)=>x, fn x=>x, fn(x,y)=>x*y);
val fact = iter(op *,1);
val power_2 = iter(fn(x,y)=>x*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);
val power = gen_iter(fn(x,y,z)=>x*z, fn x=>1, fn(x,y)=>y);