How to Program It

A great discovery solves a great problem but there is a grain of discovery in the solution of any problem.

—George Pólya

In How to Solve It, George Pólya proposes a list of questions and suggestions which may help us solve mathematical problems. The list is divided into four parts and can be summarized as follows:

1. Understand the problem:
2. What are the data?
3. What is the unknown?
4. Devise a plan of the solution:
5. Find the connection between the data and the unknown.
6. Consider auxiliary problems.
7. Carry out the plan.
8. Look back:
9. Examine the solution obtained.

In How to Program It, Simon Thompson shows how to apply Pólya's list to (functional) programming. Basically, instead of devising and carrying out a plan, we design and write a program which has inputs (data) and output (unknown).

As an example of how to apply the list to programming in Haskell, let's work through the problem of finding the missing number in a permutation of the numbers from 1 to n in which there is a missing element.

First, we have to understand the problem. We know that we have as input a possibly unsorted list of numbers from 1 to n with exactly one missing element, which we need as output. Thus, we have to write a function that takes a list of integers and returns an integer:

missingNumber :: [Int] -> Int

Additionally, we can write some examples using Haddock:

-- >>> missingNumber []
-- 1
-- >>> missingNumber [1,2,3,4]
-- 5
-- >>> missingNumber [5,3,2,1]
-- 4

In the end, we can even check these examples using doctest.

Second, we have to devise a plan. We can consider an auxiliary problem: finding the missing number in an ordered permutation of the numbers from 1 to n in which there is a missing element, which is just a matter of comparing the numbers in the permutation with the numbers from 1 to n and returning the first differing number.

If we write a function to solve the auxiliary problem and call it missingNumber', our solution becomes straightforward:

missingNumber ns = missingNumber' (sort ns) 1

Third, we have to carry out our plan, which consists solely in implementing the missingNumber' auxiliary function:

missingNumber' (n:ns) m | n == m = missingNumber' ns (m + 1)
missingNumber' _      m          = m

Finally, we have to look back and examine our solution. We can check it using doctest, which would return neither errors nor failures for our three examples. Alternatively, we can think of different ways to solve the problem; for instance, we could simply return the sum of the numbers from 1 to n minus the sum of the input numbers, which is the missing number:

missingNumber ns = sumFromOneTo n - sum ns

where

sumFromOneTo n = n * (n + 1) `div` 2

and

n = length ns + 1

For more information about how to solve problems in Haskell, take a look at Simon Thompson's Problem Solving in Haskell and Miran Lipovača's Functionally Solving Problems.