CSE 428: Quizzes

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.0, [1,2,3]); error
- elim(4, [4,3,4]); [3]
- elim([1], [[0,1],[1],[2,3]]); [[0,1],[2,3]]
- elim(fn x => 1, [ fn x => 1 , fn x => 2 ]); 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 = 0
     | f (node(t1,n,t2)) = if (f t1) > (f t2) then 1 + (f t1) else 1 + (f t2);
```
Say what is the semantics of f (only one answer, please)
- f takes a tree t and returns the sum of all elements of t
- f takes a tree t and returns the maximum of all the elements of t , plus 1 if t is not empty
- f takes a tree t and returns the height of t
- error, because < and + are not operations on trees

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

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

    fun append([],L) = L
      | append(x::K,L) = x::append(K,L);

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

 
   reduce(append, [], [[1,2],[3],[],[4,5]]);

[Pts 2] Say which of the following expressions represents a higher order function (only one answer, please. Note that reduce and append are the functions defined above)
- reduce;
- append(append([1],[2]),append([3],[4]));
- fn x => x + 1;
- (fn x => x + 1) 5;