Euler #4 : Producing Palindromes

by Nicolas Wu

Posted on 22 July 2010

Tags: ,

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.

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.

Strings

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.

Products

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]

Summary

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 Strings from other values.
  • The let construct helps us name parts of a comprehension.

Comments