<![CDATA[
CSE341 Sample Midterm handout #11
Unless otherwise noted, in writing your solutions to these problems, you may
call any of the functions available in the standard top-level environment
including:
the standard operators (~, +, -, *, /, div, mod, ::, @, ^, o,
not, andalso, orelse, <, >, <=, >=, =, <>)
the numeric function abs
the list functions hd, tl, length, rev
the conversion functions real, trunc, floor, ceil, real, ord, chr, str
the string functions implode, explode, concat, size
the standard tuple functions #1, #2, etc.
You may also call any function that is included as a problem on this exam,
whether or not you correctly solve that problem. You may call the functions
listed below that are part of the file utility.sml that we have been using
(notice that this version of map replaces the standard one):
(* sorts a list with the quicksort algorithm given a comparison function *)
(* and a list of values *)
fun qsort(f, []) = []
| qsort(f, pivot::rest) =
let fun split([], ys, zs) = qsort(f, ys) @ [pivot] @ qsort(f, zs)
| split(x::xs, ys, zs) =
if f(x, pivot) then split(xs, x::ys, zs)
else split(xs, ys, x::zs)
in split(rest, [], [])
end;
(* returns a list of the values m through n *)
infix --;
fun m--n =
if m > n then []
else m::(m + 1--n);
fun map(f, []) = []
| map(f, x::xs) = f(x)::map(f, xs);
fun filter(f, []) = []
| filter(f, x::xs) =
if f(x) then x::filter(f, xs)
else filter(f, xs);
exception illegal_reduce;
fun reduce(f, []) = raise illegal_reduce
| reduce(f, [x]) = x
| reduce(f, x::xs) = f(x, reduce(f, xs));
Unless otherwise specified, you can write your own helper functions, but you
are not allowed to use library functions like List.nth or List.last.
1. ML Expressions, 20 points. For each ML expression in the left-hand column
of the table below, indicate in the right-hand column its value. Be sure to
put any string value inside double-quotations marks ("hello" vs hello).
Assume that the following value has been declared:
val lst = [7--9, 2--5, 3--5, 12--14];
Expression Value
-------------------------------------------------------------------------------
reduce(op +, 4--7) _______________________________
reduce(op *, map(hd, lst)) _______________________________
filter(fn(x) => x mod 3 = 1, 0--15) _______________________________
map(fn(x) => reduce(op +, x), lst) _______________________________
map(fn(x) => real(x) + 0.25, 8--11) _______________________________
filter(fn(x) => length(x) = 3, lst) _______________________________
map(fn(x) => [x, x + 3], 3--6) _______________________________
reduce(op +, map(real, 5--8)) _______________________________
map(length, map(fn(x) => 3--x, 3--6)) _______________________________
reduce(op +, map(hd, map(tl, lst))) _______________________________
2. ML Types, 10 points. For each ML expression in the left-hand column of the
table below, indicate its type in the right-hand column. Assume that the
following value has been declared:
val lst = [("hello", 2), ("fun", 13)];
Expression Type
-------------------------------------------------------------------------------
lst _______________________________
hd(tl(lst)) _______________________________
tl(tl(lst)) _______________________________
fn x => (trunc(x), x) _______________________________
fn (x, y) => (y, x) _______________________________
3. Scope, 10 points. Consider the following Java program:
public class Mystery {
public static int x = 7;
public static void one() {
int x = 3;
two();
System.out.println(x);
}
public static void two() {
x = 2 * x;
System.out.println(x);
}
public static void main(String[] args) {
int x = 5;
one();
two();
System.out.println(x);
}
}
(2 points) What output does this program produce using the standard lexical
scope rules of Java?
(5 points) What output does this program produce using dynamic scope as
described in lecture?
(3 points) What value is answer bound to after executing the following code?
fun f(x) =
let val y = x + 1
val x = x + 1
in y + 1
end;
val x = 1;
val answer = f(x);
4. Curried functions, 10 points. For this problem you may call the function
curry and the curried versions of map, filter and reduce that we used in
homework #3:
(* function to convert a noncurried 2-argument function to a *)
(* curried function. For example, curry op+ returns a curried *)
(* version of the addition operator. *)
fun curry f x y = f(x, y);
(* curried versions of map, filter and reduce *)
fun map2 f [] = []
| map2 f (x::xs) = f(x)::(map2 f xs);
fun filter2 f [] = []
| filter2 f (x::xs) =
if f(x) then x::(filter2 f xs)
else filter2 f xs;
fun reduce2 f [] = raise illegal_reduce
| reduce2 f [x] = x
| reduce2 f (x::xs) = f(x, (reduce2 f xs));
As in homework #3, you may use only val definitions to solve the following
problems. You may not use "fun" or "fn" definitions to define a function.
(3 points) Define a function f1(n) that computes 2.8 * real(n)
(3 points) Define a function f2(n) that computes 13 mod (2 * n)
(4 points) Define a function f3(lst) that takes an int list as an argument
and that returns the sequence of values from the original list that are less
than 100.
5. Functions, 10 points. Implement the list function take(lst, n) which takes
a list and an int as arguments and that returns the first n elements of lst.
For example:
take([1, 3, 2, 7, 9], 3) returns [1, 3, 2]
take(["hi", "how", "are", "you"], 2) returns ["hi", "how"]
You are not allowed to call List.take to solve this problem (you must
provide an independent implementation of this standard function). You may
assume that n is greater than or equal to 0 and that the list contains at
least n elements.
6. Functions, 10 points. Implement the list function drop(lst, n) which takes
a list and an int as arguments and that returns the list formed by removing
the first n elements of lst. For example:
drop([1, 3, 2, 7, 9], 3) returns [7, 9]
drop(["hi", "how", "are", "you"], 2) returns ["are", "you"]
You are not allowed to call List.drop to solve this problem (you must
provide an independent implementation of this standard function). You may
assume that n is greater than or equal to 0 and that the list contains at
least n elements.
7. Functions, 10 points. Write a function insert that takes a list of lists
and a value as arguments and that returns the list obtained by inserting the
value at the front of each list within the list of lists. For example:
insert([1--3, 2--5, 5--7], 3) returns [[3,1,2,3],[3,2,3,4,5],[3,5,6,7]]
8. Datatypes, 10 points. Consider the following datatype for storing lists of
ints:
datatype intList = Empty | Node of int * intList;
(4 points) Write a function length that takes an intList and that returns
the number of int values in the list.
(6 points) Write a function insertSorted that takes an intList and an int as
arguments and that returns the list obtained by inserting the value into the
list so as to preserve sorted order. You may assume that the list given to
the function is in sorted order. For example:
given val lst = Node(1, Node(8, Node(19, Node(72, Empty))))
insertSorted(lst 15) returns:
Node (1,Node (8,Node (15,Node (19,Node (72,Empty)))))
9. Functions, 10 points. Write a function subsets that takes a list of values
and that returns the list of all possible subsets of the list. For example:
subsets(1--3) returns [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
It does not matter what order the subsets appear in, so the solution above
is only one possible correct solution.
]]>