CSE 428: Quizzes

Spring 2001, CSE 428: Quiz 9.4 - 29 March 2001

Please write your Name and Student ID,at the top of the page.
By default, this quiz will be returned in Section 1 (afternoon section).

[Pts 4] Consider the following definition of the function "eliminate"
```
   fun elim(x, []) = []
     | elim(x, y::L) = if x = y then elim(x,L) else y::(elim(x,L));
```
For each of the following expressions, say what is the result (including error). Remember that the two arguments of "=" must have the same type, and that it must be an equality type.
- elim(2, [1.0,2.0,3.0,2.0]); error
- elim(2, [4,3,4]); [4,3,4]
- elim([1], [[1],[2],[1,2],[1]]); [[2],[1,2]]
- elim(fn x => x, [ fn x => 1 , fn x => x ]); error
[Pts 2] Consider the following datatype representing binary trees with integer labels, and the definition of a functionfon that datatype
```
   datatype tree = empty | node of (tree * int * tree);
 
   fun f empty = empty
     | f (node(empty,n,empty)) = empty;
     | f (node(t1,n,t2)) = node(f t1, n, f t2);
```
Say what is the semantics of f (only one answer, please)
- f takes a tree t and returns the tree obtained by eliminating all the leaves of t (in this representation, a leaf is a node whose subtrees are both empty)
- f takes a tree t and returns and empty tree if t is empty or it is a leaf, otherwise it returns t
- error, because the first and the second cases return empty while the third case returns a node
- error, because the second and the third cases overlap

[Pts 2] Consider the following functions reduce and max :

    fun reduce(f, v, []) = v
      | reduce(f, v, x::L) = f(x, reduce(f,v,L));

    fun max [] = 0
      | max (x::L) = let y = max L in if x > y then x else y end;

Say what is the result of the following expression (only one answer, please)

 
   reduce(max, 0, [[1,2],[3],[4],[5,6]]);

error
6
[6]
[5,6]

[Pts 2] Say which of the following expressions represents an anonymous function (only one answer, please. Note that reduce and max are the functions defined above)
- reduce;
- max [max [1,2], max [3,4]];
- fn x => x + 1;
- fun f x = x + 1;