There was an error submitting the form

Copied to clipboard

"A great discovery solves a great problem but there is a grain of discovery in the solution of any problem." - George Pólya

Published: Jun. 8, 2015

Last updated: Feb. 9, 2022

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:

- Understand the problem:
- What are the data?
- What is the unknown?
- Devise a plan of the solution:
- Find the connection between the data and the unknown.
- Consider auxiliary problems.
- Carry out the plan.
- Look back:
- 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.

Join our community of avid readers and stay informed with the latest articles, tips, and insights delivered straight to your inbox. Don't miss out on valuable content – subscribe now and be part of the conversation!

We care about your data. Check out our Privacy Policy.