Midterm 2 (Solution)

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!). 
  General note for type inference problems: this page was graded from
  0 to 10 on a 14-point scale.  In other words, the ML pseudocode for
  mapping from points to grade was:

  fun grade(points) =
    case points of
      14 => 10
      13 =>  9
      ...
       5 =>  1
       _ =>  0;

  If you scored less than 4 points out of 14 and would prefer to get
  negative points rather than zero, contact Ben.

fun compose(f, g, x) = f(g(x));

  ('b -> 'c) * ('a -> 'b) * 'a -> 'c

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

  real * real -> real

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

  Type error: cannot unify real with int.

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

  int * int * int list -> int list

  The + operator forces numeric type.  However, I would have given
  full credit if you said that op + was an unresolved overload (not
  SML/NJ's behavior, but probably what the ML97 spec mandates), but
  nobody did.

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

  (int * int) list -> int list

  Once again, + operator induces numeric type, and I would have given
  credit for saying it was an overload error.

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

  Type error; cannot unify function cases:

       'a list              -> 'b list
       ('a -> 'b) * 'a list -> 'b list

  Worth 2 pts; partial credit for deriving the correct type for the
  second case.  Full credit was given if you pointed out that the two
  cases do not unify, and then derived the correct type for the second
  case.

fun curriedArea width height = width * height;

  int -> int -> int

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

  'a list -> 'a list -> 'a list list

  Informal reasoning:
    + z must be a list, because of tl(z)
    + x must be a list of the same type as z, because of [x, tl(z)]
    + The result type is a list of lists, because x and tl(z) are both
      lists.

(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.

    ML is statically typed, meaning that it performs its type checking operations (most of them) at compile time. Scheme, on the other hand, type checks operations as they occur (at run time), which leads to slower execution times.

  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.

    Pattern matching is (often) easier to read, and provides named access to components of a datatype. Most importantly, however, it encourages a style of programming that is less error-prone than using accessor functions. By enumerating the various patterns, we express the different cases that we must handle. The system will even warn us when presented with a sequence of nonexhaustive patterns -- encouraging us to deal with other cases we may have forgotten.

  3. Describe the differences between Scheme and ML with respect to the following features/qualities: type checking, control abstractions, data abstractions.

    Type checking: Scheme is dynamically, strongly typed. ML is statically, strongly typed. Control abstractions: both languages rely heavily on recursion, and treat functions as first-class citizens. ML has a well-defined exception mechanism, whereas Scheme doesn't define one as part of the language (there are facilities to implement it, but no standard implementation). Data abstractions: provide and use lists. ML lists are homogeneous in type, whereas Scheme's need not be. ML provides a rich set of mechanisms for information hiding (signatures), encapsulation (structures), and user-defined types (datatypes).

(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";

  ----------------------------------------------------------------------
  Several answers possible.  The most common:

  fun concatList(nil) = ""
    | concatList(x::xs) = x ^ concatList(xs);

  fun concatList strList = reduce((op ^), "", strList)

  I did not take off points if you thought reduce was a curried
  function.
(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;

  ------------------------------------------------------------------------
  Many solutions possible.  Grading scale:

  7 : Correct ML code that solves the problem

  6 : Correct ML code that solves the problem, with one minor error.

  5 : Correct ML code that works, as long as the substring match occurs
      at the first occurrence in the second sentence of the first
      string's first letter.  If I wrote

         search("hi", "hellohi")

      on your paper, then you are in this category.  If you want to
      know what this means, then try running your algorithm on the
      above function application.

  4 : Like (5), but with some additional minor error.

  3 : Either
      + Code with serious indications/beginnings of a semi-plausible
        but incorrect algorithm,
      + At least one significant conceptual error (misunderstanding ML)

  2 : Called explode on both strings, and began to break the problem
      down into cases, but no indication that you knew how to solve the
      cases.  Or, totally bizarre algorithm that I could not decipher.

  1 : Called explode correctly on both strings.

  0 : Blank answer.

(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

  ------------------------------------------------------------------------
  Almost everyone scored well on this, so I will describe only the
  decrement values (sum the decrement values and subtract from 10 to
  obtain your score):

  -2 : Forgetting to raise NoFunds.  This was the only even moderately dif

  -1 : Omitting indication that code should be in a struct

  -3 : Not understanding how to pattern-match on the constructor of a
       datatype.  If you failed at this, you did not do your own homework,
       and I would have taken off many more points if the wording of the
       question had not said that BankAccount is a tuple of a string
       and a real.

  -1 : Using an int literal instead of a real literal.

  Miscellaneous less common errors also yielded decrements.

(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;

(* answer *)

val tree = Add(Leaf(3), Mult(Leaf(4), Leaf(7)));

fun eval(Leaf(x)) = x
  | eval(Add(x, y)) = eval(x) + eval(y)
  | eval(Sub(x, y)) = eval(x) - eval(y)
  | eval(Div(x, y)) = eval(x) div eval(y)
  | eval(Mult(x, y)) = eval(x) * eval(y);

fun height(Leaf(x)) = 1
  | height(Add(x, y)) = Int.max(height(x), height(y)) + 1
  | height(Sub(x, y)) = Int.max(height(x), height(y)) + 1
  | height(Div(x, y)) = Int.max(height(x), height(y)) + 1
  | height(Mult(x, y)) = Int.max(height(x), height(y)) + 1;
(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. 
datatype 'a gtree = Node of 'a * 'a gtree list;

There were other solutions that were acceptable, but for full
credit, we were looking some sort of node with a _list_ of children,
as well as a parameterization of the element type.