Euler #4 : Producing Palindromes
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:
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
(++), we can come up with a simple version of
reverse as follows:
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.
palindrome checks to see whether or not a list of values is equal to its reversed version:
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
We can play with this function to see what happens:
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 is just a single character, so we could have written the example we saw above as follows:
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
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:
We can easily make a list comprehension based on this one that produces only palindromes:
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:
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
Strings from other values.
letconstruct helps us name parts of a comprehension.