Consider the following specification:

Write a procedure to sum the values of the two largest different items in a list of integers.

Considering inputs and outputs, we could start by writing the following header:

PROCEDURE SumTwoLargest(list : ListPtr) : INTEGER

This problem is more difficult than those we have met so far. It will not be simple to write it out straight away. Instead we need to try and simplify it into more manageable components, using several procedures rather than just one.

Firstly, let us be sure that the specification is complete. What if the list is empty? We could return zero as a reasonable answer in this case. What if there is only one unique value in the list? It would probably be reasonable to use zero as the value of the missing second item. What are the elements of the solution? We have to be able to identify maximum values. Would it help to sort the list and then find the two largest? We already have a way to find one maximum (see Largest, above) could we make use of that procedure - is finding the second largest more difficult?

These are the kinds of thinking processes that we have to go through when trying to find solutions to new problems. Here is one possible design that breaks down the original problem, and makes use of some of the earlier solutions:

Sum the two largest:
  IF the list is empty THEN
    RETURN 0
  ELSE
    Find the largest element;
    Make a copy of the list with the largest element removed;
    IF the new list is not empty THEN
      Find the largest element in the new list;
      RETURN the sum of the two values;
    ELSE
      RETURN the largest element;
    END
  END

The only part of this for which we do not already have a solution is that of removing the largest element. This will be a procedure that takes a list and the value of the elements to be removed as inputs and returns a new list as its output:

PROCEDURE CopyAndRemoveItem(list : ListPtr;
		item : INTEGER) : ListPtr

Once again, we can use our earlier models to solve this. If the list is empty, then it returns an empty list. If the item occurs at the head of the list then it does not make a copy of that item but recursively calls itself on the tail of the list. If the item does not occur at the head of the list, it makes a copy of the head and prepends it onto a copy of the list remaining after the recursive call.

PROCEDURE CopyAndRemoveItem(list : ListPtr;
		item : INTEGER) : ListPtr =
BEGIN
  IF ListIsEmpty(list) THEN
    RETURN NIL;
  ELSIF ListHead(list) = item THEN
    RETURN CopyAndRemoveItem(ListTail(list),item);
  ELSE
    RETURN ListPrepend(ListHead(list),
      CopyAndRemoveItem(ListTail(list),item));
  END;
END CopyAndRemoveItem;

So we can write the remainder of the solution as follows:

PROCEDURE SumTwoLargest(list : ListPtr) : INTEGER =
VAR
  copyList : ListPtr;
  largest, secondLargest : INTEGER;
BEGIN
  IF ListIsEmpty(list) THEN
    RETURN 0;
  ELSE
     largest := Largest(list);
     copyList := CopyAndRemoveItem(list,largest);
     IF ListIsEmpty(copyList) THEN
       RETURN largest;
     ELSE
       secondLargest := Largest(copyList);
       RETURN largest+secondLargest;
     END;
  END;
END SumTwoLargest;