Midterm 2

CSE341 Winter 2002

Name:

This Midterm is worth 60 points. The exam is closed-book, closed-notes, open-mind.

Page Possible Score
2 10
3 10
4 10
5 10
6 10
7 10
Total 60






For the purposes of this exam, assume the following functions are defined for you. 

val map = fn : ('a -> 'b) * 'a list -> 'b list

val reduce = fn : ('a * 'b -> 'b) * 'b * 'a list -> 'b

(* Return a list of elements that pass the provided predicate test. *)
val filter = fn : ('a -> bool) * 'a list -> 'a list

(* Return the greater of two provided integers. *)
val Int.max = fn : int * int -> int

(* Take a string and return it as a list of characters. *)
val explode = fn : string -> char list

(1.) [10 points total] Write the type profiles for the following ML function definitions. If the function definition causes a type error, say why (your answer should be less cryptic than the answer ML would give!). 
fun compose(f, g, x) = f(g(x));





fun average(x, y) = x + y / 2.0;





fun circumference(r) = 2 * r * 3.14;





fun bar(a, b, c) = [a, b + hd(c)];





fun why(nil) = nil
  | why((a,b)::xs) = (a+b) :: why(xs);






fun everyOther(nil) = nil
  | everyOther(f, a::b::xs) = f(a) :: everyOther(xs);







fun curriedArea width height = width * height;







fun weird x z = [x, tl(z)];

(2.) [10 points total] Short Answer. Answer any TWO of the three questions below. Correct, concise answers will be rewarded.

  1. Say why an algorithm implemented in ML might execute more efficiently (faster) than the same algorithm implemented in Scheme.
  2. When processing lists (or other datatypes), say why the use of pattern matching in function definitions (as opposed to the use of functions such as hd and tl) should be considered good style.
  3. Describe the differences between Scheme and ML with respect to the following features/qualities: type checking, control abstractions, data abstractions.

(3.) [10 points total] Perform pattern matching for each of the following pairs of ML expressions. Show the expression trees that result, and how the corresponding nodes of the trees match (or don't match, if there is a mismatch). For example, for x::y::zs and [1,2] I would answer:

3.1)(a, [b, c], d) and ("hello", [7, 8], [1, 2])

3.2)[a, b::c] and [[1, 2], [3]]

(4.) [3 points] Write a function called concatList that takes a list of strings and concatenates them together. Recall that the ^ operator can be used to concatenate two strings. 
> concatList(["hello" "goobye" "foobar"]);  
val it = "hellogoodbyefoobar";
(5.) [7 points] Write a function called search that takes two strings, and returns true iff the first string is found somewhere within the second string. Hint: Use the built-in function explode to turn strings into lists of characters. The expected type profile and some examples are shown below: 

> search;
val it = fn : string * string -> bool
> search("bok", "hoboken");
val it = true;
> search("art", "barbar") 
val it = false;

(6.) [10 points] Below is the signature for a BankAccount structure. Your job is to provide an implementation for the structure. It should consist of definitions for a datatype, an exception, and the 5 functions described below. 
structure BankAccount :
  sig
    (* An Account is a tuple of a name and a balance *)
    datatype Account = Account of string * real
    exception NoFunds
    (* Given an Account, return its balance. *)
    val balance : Account -> real
    (* Given an Account, return the owner's name. *)
    val name : Account -> string
    (* Create a new Account with the given owner, and zero funds. *)
    val newAccount : string -> Account
    (* Deposit this amount into the given Account. *)
    val deposit : real * Account -> Account
    (* Withdraw this amount from the given Account.  Raises NoFunds if
       there is not enough money. *)
    val withdraw : real * Account -> Account
  end

(7.) [7 points] Below we've provided a definition for a datatype called Tree which can be used to represent expression trees. Your job is to write the following:
  1. Construct a sample tree (called tree) which represents the expression 3 + 4 * 7. (For full credit, the tree should represent the fact that * has higher precedence than +.)
  2. Write a function called eval, which evaluates an expression tree. It takes a Tree and returns an integer.
  3. Write a function called height, which takes a Tree and returns an integer that is the height of that tree. 
datatype Tree = Leaf of int | Add of Tree * Tree | Sub of Tree * Tree |
                Mult of Tree * Tree | Div of Tree * Tree;
(8.) [3 points] Give just the the definition for a generalized tree datatype. Nodes in a generalized tree may have any number of children. The labels/elements of your tree should be of any type.