Problem solving: recognising palindromes

Simon Thompson
Computing Laboratory
University of Kent, Canterbury, UK

This is an account of a problem solving example covered `live' in a first year lecture at the University of Kent.

The example: palindromes

We covered the example of recognising palindromes, which take the form

"Madam I'm Adam."

Understanding the problem

We started by working out exactly what a palindrome is: the first stage of the problem solving process.

A palindrome is a string of text which reads the same backwards and forwards, if

we disregard the punctuation (punctuation marks and spaces) in the string;
we disregard the case (upper or lower: that is capital or small) of the letters in the string.

At this stage we can start to say something about the Haskell program we are to write. We will be writing a function, whose name and type we can give at this point. We will call the function

palin

What is its type? It will have an argument: the string we are checking; the result of the test will be a Boolean, so

palin :: String -> Bool

Starting the design

Now we know what we are aiming at, we can try to design the solution to the problem. A number of strategies are given in the sheets mentioned above, including looking for related problems, functions we already know which we might use, and trying to break the problem into parts which we can solve separately. The palindrome problem breaks into two parts:

disregard the punctuation and case, and
reverse the string and compare it with its original form.

We can try to solve these two separately. Suppose that the string st contains no punctuation and is in lower case, then we just need to do the second task:

palin st = (reverse st == st)

which says exactly that we have to reverse the string (reverse st) and compare it with the original ( ... == st). This means that we have to solve the problem of reversing a string:

reverse :: String -> String

How can we solve the whole problem? We need to do the same, but to a string which has had its punctuation and case disregarded:

palin st = (reverse st' == st')
           where
           st' = disregard st

where the function which disregards punctuation and case is

disregard :: String -> String

which takes and returns a String.

Carrying on

Now, how far have we got? Our problem has been broken down to two simpler problems: those of defining reverse and disregard. Now we look at these in turn.

To reverse a string, which is a list of characters ([char]), we need to define the function from scratch (unless we look in the Haskell standard prelude!). How to start with this? We can think of this being written in stages, left hand side first:

reverse :: String -> String

reverse []     =
reverse (a:st) =

which are the two cases of an empty string and a non-empty string whose first element is a and whose remainder (or tail) is st.

An empty string reversed is empty:

reverse []     = []

while in the general case we can be guided by an example. In this sort of definition we define reverse (a:st) using reverse st. Take the example "door". In reversing the tail we have "roo" and we get what we want by sticking "d" at the end. So,

reverse (a:st) = reverse st ++ [a]

where ++ joins together two strings and [a] is the string made up of the single character a.

The final problem to solve is to find disregard which as we saw above consists of two parts:

remove punctuation;
change capital letter to small letters.

and we can solve these two separately with

remove :: String -> String
change :: String -> String

We make disregard by applying these in turn. There are two ways we might do this:

disregard st = remove (change st)
disregard st = change (remove st)

Which might we choose? Here is an example of reflecting upon our design par excellence; we can choose this without having implemented either function. We choose to do the latter, since under this definition we only change those items which remain in the string. Incidentally, we can write this definition in a different way again:

disregard = change . remove

which says that the disregard function is made by composing the functions change and remove; first remove is applied, then change is applied to the result.

The last steps

It remains to define remove and change. The former is defined by the familiar recursion pattern:

remove :: String -> String

remove []     = []
remove (a:st) =

What about the (a:st) case? There will be two cases, depending whether a is a punctuation character or not:

remove (a:st) 
  | notPunct a	= ....
  | otherwise   = ....

In the first case, a goes into the list

remove (a:st) 
  | notPunct a	= a : ....
  | otherwise   = ....

In both cases the remainder of the result is got by removing punctuation from st:

remove (a:st) 
  | notPunct a	= a : remove st
  | otherwise   =     remove st

where we can check whether we have punctuation or not in a number of ways:

notPunct :: Char -> Bool

notPunct ch = not (ch=='.' || ch == ',' || .... )

where we say that ch is not one of the punctuation characters, or

notPunct ch = isAlpha ch || isDigit ch

where we say that we have either a letter or a character.

Finally, we need to think how to define

change :: String -> String

Here we need to affect each character in the list by converting it;

change []     = []
change (a:st) = convert a : change st

and where

convert :: Char -> Char

convert ch 
  | isCap ch	= decode (code ch + offset)
  | otherwise   = ch                      
     where
     offset = code 'a' - code 'A'

isCap :: Char -> Bool

isCap ch =  'A' <= ch && ch <= 'Z'

Conclusion

This example shows how the problem solving approach applies in Haskell, and how the approach can help you to get started with a complex problem.

An executable version of the program can be found here.

Created 21 November 1996. Last modified 26 August 1997.