Exercise 1
----------
Exercise 8.1 in Mitchell's book


Exercise 2
----------
Exercise 8.3 in Mitchell's book


Exercise 3
----------
Exercise 8.4 in Mitchell's book


Exercise 4
----------
Exercise 8.7 in Mitchell's book


Exercise 5
----------
(Taken from Paulson's book "ML for the working programmer")
Given a certain amount of money and a list of coin values, we would like to receive change using the largest coins possible. This is easy if the coins values are supplied in decreasing order. The following naive algorithm implements it:


fun change (coinvals, 0)         = []
  | change (c::coinvals, amount) =
      if amount<c then change(coinvals, amount)
                  else c :: change(c::coinvals, amount-c);


The first argument is the list of valid coins and the second one is the given amount to be changed.
The algorithm returns the first way of making change: if the target amount is zero, no coins are required; if the largest coin value c is too large, discard it; otherwise use it and make change for the amount less c.

Notice that the algorithm is NOT EXHAUSTIVE (you will get the following message: "Warning: match nonexhaustive"). The algorithm is less trivial than it seems. For the following cases

- change([], 12);
- change([5,2], 16);
- change([5,2], 18);

it will give as an answer: "uncaught exception Match [nonexhaustive match failure]". However, it works well in many other cases like the following:

- change([5,2], 12);
val it = [5,5,2] : int list

- change([5,2], 14);
val it = [5,5,2,2]: int list

The reason is that the algorithm is greedy, trying to express the given amount with the largest coin first and then trying with the rest of the coins (for instance, in "change([5,2], 16)", it tries 5,5,5 and then 1, which is not a valid coin).

In order to design a better algorithm we need "backtracking": responding to failure by undoing the most recent choice and trying again. One way of implementing backtracking is by using exceptions. Write a function "changeBack : int list * int -> int list" in ML which implements a backtracking algorithm for solving the above problem using exceptions (define "exception Change;"). These are some examples of expected results: 

- changeBack([5,2], 17);
val it = [5,5,5,2] : int list

- changeBack([], 12);
uncaught exception Change

- changeBack([5,2], 16);
val it = [5,5,2,2,2] : int list