I could write this post by showing directly my solution and why it is efficient, but this is a kind of exposition that implies arrogance. Instead, I want to show you how functional reasoning allows you to write efficient programs.
To jump directly to the problem, we’ll start with a definition: a palindrome is a string read the same from start to end and from end to start, ignoring blank characters, punctuation symbols, and whether or not a letter is in lowercase or uppercase.
– this is a palindrome: “Madam, I’m Adam”
– this is not a palindrome: “This man is working hard”
So the definition of a palindrome is easy to understand, and to test that a string is a palindrome or not is easy from the standpoint of a reader.
Let’s solve it using functional programming instead of imperative programming. The first thing to notice is that we have to test if a character is a letter or not. In Haskell, in the library Data.Char exists a function isAlpha :: Char -> Bool which tests if a character is a letter or not.
Also, in Haskell we have a function (imported from Data.Char) which coverts a letter in lowercase: toLower :: Char -> Char.
The first thing to do with a string (let’s note it str) is to convert it in lower letters. We know that a string is a list of characters, so we’ll map toLower on each character of the string str:
stringToLower :: String -> String
stringToLower str = map toLower str
Than, we have to remove from consideration every character in the string that isn’t a letter; that means we have to filter the characters from the string which are not letters. We can do that using the function filter from Haskell:
stringletters :: String -> String
stringletters str = filter isAlpha str
Next, we combine the 2 functions defined untill now into one, in order to obtain the string str in lowercase and consisting only of its letters:
stringLowerLetters :: String -> String
stringLowerLetters = stringToLower.stringletters
Another function that exists in Haskell is reverse :: [a] -> [a], defined generally, which takes a list and returns the same list, but in reverse order!
Now we’re ready to construct the function which states if a number is palindrome or not:
isPalindrome :: Srting -> Bool
isPalindrome str = stringLowerLetters str == stringLowerLetters(reverse str)
Here comes an importat point to make! Notice that in the above definition of isPalindrome, we used 2 times the function stringLowerLetters. But in functional programming, when we construct functions from another functions, we can reason about functional equations. This is very importat, because it allows one to view clearly the problems of efficiency in terms of functional composition.
In our definition, let’s see that stringLowerLetters . reverse = reverse . stringLowerLetters , which is the same with saying that converting string to lower letters, than reversing it, is the same with reversing the string, than converting it to lower letters. That permits for the following definition of isPalindrome, which uses stringLowerLetters only once! This is a huge improvement when you’re working with strings of large lengths.
The more efficient definition is the following::
isPalindrome :: String -> Bool
isPalindrome str = s1 == reverse(s1)
where s1 = stringLowerLetters str
Here is an importand observation to make: composing programs from small functions allows one to reason about larger programs, and the properties of the small function components permits for simplifications and optimizations of the larger ones. We can say in a more obvious way, in the isPalindrome function, that simpler means more efficient.
Back to our problem, this is the final program in Haskell:
> import Data.Char
> import Data.List
> stringToLower :: String -> String
> stringToLower str = map toLower str
> stringletters :: String -> String
> stringletters str = filter isAlpha str
> stringLowerLetters :: String -> String
> stringLowerLetters = stringToLower.stringletters
> isPalindrome :: String -> Bool
> isPalindrome str = s1 == reverse(s1)
> where s1 = stringLowerLetters str
As an exercise, you can write an efficient algorithm for isPalindrome using recursion. How would you do it?
If you want to learn more about functional programming, check one of the best books about it (Richard Bird – Thinking Functionally with Haskell)