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.
fn f => fn g => fn x => f (g x);
fn f => fn (x,y) => f x;
fn x => fn f => (x, (f x));
fun f g x = g (g x);
fun f g x = (g g) x;
fun f g x y = g(y,x);
fun f g x = if x then true else g (f g true) x;
fun f g x y = if x then y else g (x + y);
fun f nil = nil | f (x :: l) = (x :: nil) :: (f l);
fun f nil = nil | f (g :: l) = g (f l);
fun f nil = nil | f (nil :: l) = nil :: nil | f l = l;
fun f nil = nil | f (nil :: l) = l :: nil | f l = l;
fun f nil k = nil | f l nil = nil | f (x :: l) (y :: k) = (x,y) :: (f l k);
('a -> ('b -> 'c)) -> ('a -> 'b) -> ('a -> 'c)
('a -> 'b) -> ('b -> 'a)
('a * 'b) -> 'a
'a -> ('a * 'b)
('a -> ('b -> 'c)) -> (('a * 'b) -> 'c)
'a -> 'b -> 'a * 'b
'a -> 'b -> 'a
('a * 'b) -> ('a -> 'c) -> ('c * 'b)
Hint: To show that a type A is inhabited, it is sufficient
to show that there exists an ML term M which has type A.
To show that a type A is not inhabited, one can proceed in two ways:
datatype color = white | red | green | blue; datatype 'a btree = emptybt | consbt of 'a * 'a btree * 'a btree; datatype 'a tree = ctree of 'a * 'a tree list;For each of the following functions, say whether it is typeable in ML (given the above declarations), and, in the positive case, give its most general type.
fun f white = [] | f c = [consbt(c,emptybt,emptybt)];
fun f emptybt = white | f t = red;
fun f emptybt = white | f (ctree(c,l)) = c;
fun f (ctree(c,l)) = c :: (f_aux l) and f_aux [] = [] | f_aux (t :: l) = (f t) @ (f_aux l);