=========================preview======================
(comp251)[2010](f)midterm~wfli^_10186.pdf
Back to COMP251 Login to download
======================================================
COMP 251 2010 Fall Semester Midterm Exam

Date: Thursday, Oct 14, 2010 Time: 7C9pm Instructions: (a) This exam consists of 6 questions on 12 pages. The total mark is 100.
(b)
Attempt ALL questions using pen. NO pencil please.

(c)
Write ALL answers in the space provided in the exam paper.

(d)
The last 2 pages are provided for your rough work.

(e)
Unless otherwise stated, for any question that requires writing an SML program, you may use any SML library function or write additional helper functions. However, your program must be complete in the sense that it can be run in the SML interpreter in our lab. Thus, if you want to use any special library function, make sure you also open up the library in your code to show which library you are using.


Name
Student ID
Lab Section

For T.A. Use Only

Question Score
1 / 20
2 / 5
3 / 10
4 / 17
5 / 20
6 / 28
Total / 100

Problem 1 (20 points) For each of the following SML expression, indicate if there is any error. Just say yes (if there is an error) or no (if there is no error). No explanations are required. For each question, you will get 2 points for a correct answer, zero for no answer, and -1 for an incorrect answer.
Yes / No
(a) if 1=2 then true else 0; Y
(b) 1.0 = 1; Y
(c) 1.0 = 1.1; Y
(d) true andalso (1 mod 0)=1; Y
(e) true orelse (1 mod 0)=1; N
(f) fun foo x = 1 | foo 1 = 1; Y
(g) fun foo 1 = 1 | foo x = 1; N
(h) fun foo (x::xs) = xs | foo [] = []; N
(i) fun foo [] = [] | foo (x::xs) = xs; N
(j) fun foo [] = [] | foo x::xs = xs; Y

Problem 2 (5 points) What is the value of the following SML expression?

let
val x = 1
fun add x y = x+y
in
add (x+9) 9
end;
Answer: 19
Problem 3 (10 points) Write the SML occurs function of the following type
occurs = fn: a -> a list -> bool
Given a list L and an item x, occurs x L returns true if x is in L, and false otherwise. Do not introduce any helper functions.
Answer:
fun occurs x [] = false | occurs x (y::ys) = if x=y then true else (occurs x ys);
Or,
fun occurs x [] = false
| occurs x (y::ys) = x=y orelse (occurs x ys);

Problem 4 (17 points) Write the SML count_list function of the following type
count_list = fn: a list -> int
Given a list L, count_list L returns the number of distinct elements in L. For exam-ples:
count_list [1,2] returns 2 count_list [1,2,1] returns 2 count_list [1,2,1,2,1] returns 2 count_list ["hello", "world", "and", "hello", "you"] returns 4
Answer:
Solution 1:
(* occurs *)
fun occurs x [] = false
| occurs x (y::ys) = if x=y then true else (occurs x ys);

(* binary count_list helper function *) fun count_list2 [] L = 0 | count_list2 (x::xs) L = if (occurs x xs) then count_list2 xs L else 1+ (count_list2 xs (x::L)); fun count_list L = count_list2 L [];
Solution 2:
(* delete an item from a list *)
(* this is a recursive definition. can be defined using fi