<![CDATA[
CSE341 Midterm, Winter 2007
Name of Student_______________________________________________________________
Unless otherwise noted, 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 _____ 6 Functions 5 _____
2 ML Types 10 _____ 7 Functions 10 _____
3 Scope 10 _____ 8 Datatypes 10 _____
4 Curried Functions 10 _____ 9 Functions 10 _____
5 Functions 5 _____ 10 Functions 10 _____
Total _____
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
-------------------------------------------------------------------------------
map(hd, map(tl, lst)) _______________________________
map(fn x => reduce(op +, x), tl(lst)) _______________________________
map(fn(x, y) => x + y, [(1, 3), (4, 5)]) _______________________________
reduce(op *, map(length, lst)) _______________________________
filter(fn(x) => x div 4 = 2, 1--15) _______________________________
length(reduce(op @, lst)) _______________________________
map(fn(x) => x * x, map(hd, lst)) _______________________________
map(fn(x) => (x, 2 * x), 1--4) _______________________________
reduce(op +, map(fn(x) => 2 * x - 4, 10--15)) _______________________________
map(fn(x) => 2--x, 3--5) _______________________________
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 assuming the
expression was added to the standard top-level environment. Assume that the
following value has been declared:
val lst = [8--12, 17--22, 3--9];
Expression Type
-------------------------------------------------------------------------------
lst _______________________________
(hd(lst), hd(hd(lst))) _______________________________
hd o rev o explode _______________________________
fn x => x::[x] _______________________________
fn (x, y) => ((x + y), x, y) _______________________________
3. Scope, 10 points. Consider the following Java program:
public class Mystery {
public static int x = 8;
public static int y = 3;
public static void one() {
x = x + 10;
y = y + 20;
System.out.println(x);
System.out.println(y);
}
public static void two(int x) {
y = y + 100;
one();
}
public static void three() {
int y = 7;
one();
}
public static void main(String[] args) {
int x = 4;
int y = 6;
one();
two(2);
three();
System.out.println(x);
System.out.println(y);
}
}
(2 points) What sequence of numbers does this program output using the
standard lexical scope rules of Java (comma-separated list is okay)?
(5 points) What sequence of numbers does this program output using dynamic
scope as described in lecture (comma-separated list is okay)?
(3 points) What value is answer bound to after executing the following code?
val x = 3;
fun f(n) =
let val y =
let val y = x + 2
val x = 4
in x + y
end
in x + y + n
end
val x = 1;
val answer = f(8);
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(str) that takes a nonempty string as an
argument and that returns the last character of the string
(3 points) Define a function f2(n) that takes an integer n and that returns
true if and only if n is not a factor of 120
(4 points) Define a function f3(n) that returns a list of the first n
even integers assuming n is greater than 0 (e.g., f3(3) returns [2,4,6])
5. Functions, 5 points. Write a function member(v, lst) that takes a value v
and a list lst as arguments and that returns true if and only if v appears
at least once in lst.
6. Functions, 5 points. Write a function pow2(n) that takes an integer n as an
argument and that returns a list of the first n powers of 2 starting with 1
(2^0). For example, pow2(5) should return [1,2,4,8,16]. Your function must
run in O(n) time, which means that it should require approximately n
multiplications or additions. You may assume that n is not negative.
7. Functions, 10 points. Write a function partitionModN(lst, n) that takes a
list of integers lst and an integer n as arguments and that returns a list
obtained by partioning the list into n segments (possibly empty) using the
mod operator. The result should begin with all values that are 0 in mod n,
followed by the values that are 1 in mod n, followed by the values that are
2 in mod n, and so on, ending in the values that are (n - 1) in mod n. It
does not matter what order the elements appear in within any segment.
partitionModN([8, 7, 4, 3, 1, 5, 14, 2, 19], 4) could return
[8, 4, 1, 5, 14, 2, 7, 3, 19] or
[4, 8, 5, 1, 2, 14, 19, 3, 7] (and several others)
Write your solution to function partitionModN below.
8. Datatypes, 10 points. Recall the datatype we discussed in lecture for
storing binary trees of integers:
datatype intTree = Empty | Node of int * intTree * intTree;
(3 points) Write a function product that takes an intTree and that returns
the product of the values in the tree. Assume that the empty tree has a
product of 1.
(7 points) Write a function sameStructure that takes two intTrees and that
returns true if and only if the trees have the same structure. Two trees
are considered to have the same structure if they have the same number of
nodes and the same pattern of left and right subtrees. It does not matter
what values are stored in the trees in making this determination (only the
structure matters).
Questions 9 and 10 involve what is called a directed graph. A directed graph
is composed of a set of vertices and edges. We'll assume the vertices are
numbered with integers and that the edges are specified as an unordered list of
int * int tuples. For example, consider the following list:
val lst = [(1, 2), (2, 3), (2, 4), (4, 5), (5, 3)];
Each pair of values indicates a directed edge connecting two vertices of the
graph. The pair (1, 2) indicates that there is an edge from vertex 1 to vertex
2. The pair (2, 3) indicates that there is an edge from vertex 2 to vertex 3.
And so on. Below is the resulting graph.
1 ---> 2 ---> 3
| ^
v |
4 ---> 5
Notice that the edges have a specific direction. There is an edge from vertex
1 to vertex 2, but not in the other direction. Although there are no examples
in this graph, it is possible to have a connection in both directions between
a pair of vertices if the list contains both (v1, v2) and (v2, v1).
9. Functions, 10 points. Write a function adjacent(v, lst) that takes a
vertex v and a list of edges lst as arguments and that returns a list of
all vertices that have an edge starting with v. For example, given the
previous definition:
adjacent(1, lst) would return [2]
adjacent(2, lst) would return [3, 4] (any order)
adjacent(3, lst) would return []
adjacent(4, lst) would return [5]
adjacent(5, lst) would return [3]
As indicated above, if there is more than one adjacent vertex, your
function can list them in any order. Write your solution to function
adjacent below.
10. Functions, 10 points. Write a function reachable that takes a vertex and a
list of edges as arguments and that returns a list of all vertices that are
reachable from the given vertex. A vertex is considered reachable if it is
adjacent or if it is reachable from an adjacent vertex. For example, given
the definition above:
reachable(1, lst) would return [2,3,4,5] (any order)
reachable(2, lst) would return [3,4,5] (any order)
reachable(3, lst) would return []
reachable(4, lst) would return [3,5] (any order)
reachable(5, lst) would return [3]
As indicated above, if there is more than one reachable vertex, your
function can list them in any order. Your function must deal with the
possibility of a cycle. For example, if the original graph had included
the connection (3, 4), then the following answers would change:
reachable(3, lst) would return [3,4,5] (any order)
reachable(4, lst) would return [3,4,5] (any order)
reachable(5, lst) would return [3,4,5] (any order)
Notice that a vertex can be reached from itself if there is a sequence of
adjacent vertices that starts and stops at the same vertex. Write your
solution to function reachable below.
]]>