# Case Analysis

Consider the following specification:

``` Write a procedure to find the maximum value in a list. ```

Can we use the ideas above to solve this? We could quickly sketch out a procedure header

``````
PROCEDURE Largest(list : ListPtr) : INTEGER
```
```

Modula 3 also has a built in function, MAX, to give the maximum of two integers, which will come in useful. Now as we begin to fit a solution around the paradigms we have seen, we find a problem; what do we do if the list is empty? It does not make sense to find the largest value in an empty list so we either need to raise an exception in this case, or return a special value that will mean `none' to any caller of the procedure. However, because the values in the list are INTEGERs, it would not be reasonable to reserve one of these (0, say) for this purpose, as that would be impossible to distinguish from the case of a non-empty list that does actually contain that particular value as its largest. Rewriting the header to use an exception we have:

``````
EXCEPTION EmptyList;
PROCEDURE Largest(list : ListPtr) : INTEGER RAISES {EmptyList}
```
```

Now can we complete the procedure along the lines we used earlier?

``````
PROCEDURE Largest(list : ListPtr) : INTEGER RAISES {EmptyList} =
BEGIN
IF ListIsEmpty(list) THEN
RAISE EmptyList;
END;
END Largest;
```
```

This uses MAX to return the larger of the item at the head of the list and the largest value in the remainder of the list. However, something is wrong. We considered the case of an empty list, but what happens when there is only one item in the list? The first time Largest is called, ListTail will produce an empty list and this will raise an exception in the recursive call to Largest. Indeed, the recursive call to Largest at the end of the list will always have this effect, no matter how long the original list. The problem is that MAX needs two values to be compared, but a list of length 1 only contains a single value. How can we solve this? Just as we check for an empty list, one way is to check for a list with only one item when the item at the head must be the largest.

``````
PROCEDURE Largest(list : ListPtr) : INTEGER RAISES {EmptyList} =
BEGIN
IF ListIsEmpty(list) THEN
RAISE EmptyList;
END;
IF ListIsEmpty(ListTail(list)) THEN
(* List of only one item. *)
ELSE
(* There are at least two items in the list. *)
END;
END Largest;
```
```

This serves to illustrate that, as well as checking for empty lists, we sometimes need to check for lists of only one item before processing them fully - another useful piece of knowledge to add to your problem-solving toolkit!

If you feel really confident, you might like to find an alternative solution to mine by not checking for a single item but catching the exception raised at the end of the list.
To
Previous Page

To Overview

To Next Page