Removing spaces

Let’s call this version of the function isPalindromePhrase.The variable name is not particularly important, but we’ll call it phrase instead of word this time, just to remind ourselves that we’re thinking of this input as something that might have spaces in it.

Just like before, we’re going to get some more mileage out of the isPalindrome function – we write can write our new function by applying isPalindrome to the output after the space removal.

Remember that a String is a list of characters, so to do anything with it, we’re going to want a case expression again, with cases for the two list constructors, empty and non-empty.

We’ll do something a little different this time, though. We’ll cover the non-empty situation with two cases – first the case where the head of the list is a space, and then another case for everything else.A case expression can have as many patterns you like, as long as each pattern is appropriate for the type – we’re matching a list, so our patterns all have to involve [] or (:). In this example, we have two patterns involving the (:) constructor. The order matters here, because the first pattern that matches is the branch that gets taken.

1. What does it mean to remove all of the spaces from an empty string? There are no spaces to remove, because there are no characters at all, so we should get back the empty string, unchanged.
2. For the next case, we have a string that starts with a space, and then might have some other characters after it. So we want to get rid of that space and consider only the remainder. So we can apply the withoutSpaces function to just the remainder. Recursion!
3. If that first character is anything other than a space, then we do want it to appear in the output. We still need to apply withoutSpaces recursively to the remainder, but in this case we want to make sure we keep that initial character so we don’t lose it. So we’ll cons that first character back onto the result.

It’s always a good idea to try it out:

λ> withoutSpaces "taco cat"
"tacocat"

λ> isPalindrome "taco cat"
False

λ> isPalindromePhrase "taco cat"
True

But let’s not stop here, because I’m not sure that spaces are the only kind of character that’s going to cause us problems.

This is a classic palindrome phrase, but there’s all sorts of spaces and punctuation in there that we have to be able to look past to see that it’s a palindrome.

Perhaps what we should have done is make this function more general, so that it could remove other things. Rather than only limiting ourselves to thinking about spaces, let’s add a parameter so that we can use this function with any criteria for what kind of characters to keep.

It has a very similar type to withoutSpaces, because it’s a string-modifying function – its input is a String, and its output is a String. But this time we’ve added another parameter up front: this Char -> Bool function that selects the characters we want.

filter is actually already a function in Prelude, so we don’t have to write it. Again, we’re going to write it anyway just to show how it’s done, and we’ll call ours something slightly different.

A function that returns a Bool is often called a predicate, so that’s what we’ll call this first variable. The second parameter is the string we’re going to filter.

This myFilter function will follow the same general outline as withoutSpaces, because what it does is similar. Filtering an empty string, regardless of the predicate, should yield the empty string, because there are no characters to filter.

We now have to make use of this additional first parameter. For each character in the input string, when this predicate returns True we’ll keep it, and when it returns False we’ll discard it. So when we have a non-empty string, we need to apply predicate to the first character. What we do next depends on what the predicate says about the first character.

1. When predicate first is True, then first is something we want to keep, so after we recursively apply myFilter predicate to the remainder, we will cons first back onto the result so that we keep that character.
2. When predicate first is False, then we only return the result from filtering the remainder.

The actual filter function in Prelude is more general than the one we’ve defined here.API documentation for filter

λ> :type filter
filter :: (a -> Bool) -> [a] -> [a]

We had a Char predicate, and we filtered a list of characters to get a modified list of characters. The Prelude function called filter accepts a predicate over any type a, and can filter a list of a to return a modified list of a. When the type variable a is Char, we get the same type as myFilter.

But it could be anything. Next we’ll give an example to think about how the evaluation of the filter function proceeds, and we’ll use a list of numbers. Let’s say we want all the even numbers out of a list. There’s a Prelude function called evenAPI documentation for even which is a predicate on numbers, and it tells us whether a number is divisible by two.

In this first incarnation of the list, the head is 1, and the tail is [2,3,4].

Since the predicate even is False for the input 1, we will take the branch that discards the first value, and we are left with filtering the remainder of the list, [2,3,4].

This time, the first item, 2, does satisfy the predicate even, so evaluation continues along the other branch. We can rewrite this expression once more. The two gets pulled out to the left, and we have a recursive application of filter even to the remainder, [3,4].

3 is discarded, and we are left with 4 as the first item, and [] as the remainder.

4 is even.

Any time when we filter an empty list, we get an empty list. So the final application reduces to [].

Written in the more concise list notation, this ultimate result is the list [2, 4].

So, first we wrote withoutSpaces, and then we wrote the more general function myFilter. As is often the case when we write a function and then write a more general variant of it, we can now go back and clean up some code by rewriting the first function in terms of the second one. This tends to simplify things and reduce the overal amount of code.

We can think of withoutSpaces now, perhaps a little more clearly, as filtering on some predicate – notSpace – we want to keep only characters that aren’t spaces.not is a function that we haven’t seen yet, but it does what you might expect – it takes a Bool and produces the opposite value, so not True is False, and not False is True.

Or, now that that definition is so short, maybe we don’t need that function at all and we can just use myFilter directly in the palindrome tester. Since withoutSpaces phrase is equal to myFilter notSpace phrase, we can substitute one in place of the other. Getting rid of a function definition like this is often described as inlining the definition.

We still have not accomplished our goal of solving the “madam, I’m adam!” problem, but we have made it easier.

The Data.Char module has a lot of Char -> Bool functions. Look through the list to see if there is a function here that’s a suitable argument to myFilter that will make madam, I'm adam! recognizable as a palindrome.