CSE 428: Quizzes

Spring 2001, CSE 428: Quiz 10.1 - 11 April 2001

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

[Pts 2] Consider the following datatype declaration:
```
   datatype 'a tree = empty | node of 'a tree * 'a * 'a tree;
```
In this declaration, 'a is (only one answer please):
- a variable that must have been declared before
- a type parameter that stands for any type
- the name of the type that we are declaring. (Here, in particular, we are declaring the type 'a as a function on trees.)
- the type of the functions which can use this datatype

[Pts 2] For each of the following functions on the above datatype, say whether it is polymorphic (in the sense that it accepts in input trees with labels of any type) or not

fun nodes empty = 0  (* returns the number of nodes *) 
  | nodes (node(t1,n,t2)) = nodes(t1) + 1 + nodes(t2);    yes

fun sum empty = 0  (* returns the sum of all nodes *)
  | sum (node(t1,n,t2)) = nodes(t1) + n + nodes(t2);      no

fun symm empty = empty  (* returns a symmetric tree *)  
  | symm (node(t1,n,t2)) = node(symm t2, n, symm t1);     yes

fun add2 empty = empty  (* adds 2 to all the nodes *) 
  | add2 (node(t1,n,t2)) = node(add1, n+2, symm t1);     no

[Pts 2] In general, the entities defined by a logic program are (only one answer, please)
- functions
- relations
- logical connectives
- local variables
[Pts 4] Consider the usual definition of the append predicate:
```
   append([],L,L).
   append([X|L],K,[X|M]) :- append(L,K,M).
```
For each of the following queries, please indicate all the answers that are returned (assuming that we interactively keep asking for more answers). If no answers are returned, write "no". If the query generates an error, write "error".
- ?- append([1],[2],L). L = [1,2]
- ?- append(L,[1],[1,2]). no
- ?- append([X],[Y],[1,2]). X = 1 Y = 2
- ?- append(L,K,[1,2]). L = [ ] K = [1,2] ; L = [1] K = [2] ; L = [1,2] K = [ ]