by Nicolas Wu

Posted on 22 July 2010

Hurrah! Time for another puzzle!

Find the largest palindrome made from the product of two 3-digit numbers.

A palindrome is just a list, which, when reversed, is the same as itself. Our approach to solving this problem will be to first define a function that recognises palindromes, before producing all the products of three digit numbers, and restricting those numbers to those which are palindromes.

Recognising a palindrome requires us to be able to reverse a list of elements. Before we define a reversing function, we’ll define a function which concatenates (glues) two lists together. Putting two lists together by concatenation is extremely useful, and the operator `(++)`

is provided in the prelude for us. Here’s its definition:

```
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
```

The definition says that when we are adding an empty list to some list `ys`

, then we simply return `ys`

. If the list is not empty and is instead some `(x:xs)`

then we add `x`

to the front of the result of sticking `xs`

and `ys`

together.

Using `(++)`

, we can come up with a simple version of `reverse`

as follows:

```
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
```

This definition says that when a list is made up of `(x:xs)`

, we create a singleton list, `[x]`

, and add this to the end of reversing `xs`

by using our concatenation operator. Again, `reverse`

is provided for us in the prelude since it is an often used function.

The function `palindrome`

checks to see whether or not a list of values is equal to its reversed version:

```
> palindrome :: (Eq a) => [a] -> Bool
> palindrome xs = xs == reverse xs
```

This function only works when the type `a`

is a member of the `Eq`

class, which simply provides the `(==)`

operator for us.

The next thing we need in order to solve our problem is to have a means of turning a number into a list of its digits. Haskell provides us with a function `show`

which turns basic types into strings. This function works on any type of value which has a type that is a member of the `Show`

class:

`show :: (Show a) => a -> String`

We can play with this function to see what happens:

```
*Main> show 4567
"4567"
```

The value which is returned is a `String`

, which is an example of a type synonym for a list of `Char`

values, which has type `[Char]`

. Each `Char`

is just a single character, so we could have written the example we saw above as follows:

`"4567" == ['4','5','6','7']`

This is exactly what we need, since we can now check to see if this list is indeed a palindrome by looking at the output of `show`

.

We finish this problem by writing a list comprehension that produces all the products of values that have three digits, and then modifying this comprehension to ensure that its values are all palindromes before taking the maximum value.

Since multiplication is commutative, in that `x * y = y * x`

, we can save ourselves a lot of work by making sure that the `y`

values we produce are always greater than or equal to `x`

. The following list produces all the `x * y`

values we require:

`[x * y | x <- [100 .. 999], y <- [x .. 999]]`

We can easily make a list comprehension based on this one that produces only palindromes:

```
[z | x <- [100 .. 999], y <- [x .. 999],
let z = x * y, (palindrome . show) z]
```

This makes use of a `let`

expression, that creates a variable `z`

which we can then ensure is a palindrome.

Our final answer makes use of the function `maximum`

, which takes the maximum value in a list of elements that have an order:

```
> euler4 = maximum
> [z | x <- [100 .. 999], y <- [x .. 999],
> let z = x * y, (palindrome . show) z]
```

In this article we’ve seen how list comprehensions can be used to produce lists of palindromes. Here are the highlights of what we’ve seen:

- Lists can be concatenated together using
`(++)`

. - The
`show`

function produces`String`

s from other values. - The
`let`

construct helps us name parts of a comprehension.