In this segment, we’ll learn how to solve what computer scientists (in our house) refer to as The Taco Cat Problem.
λ> isPalindrome "taco cat"False
The strategy here can be very similiar to what we did to handle capital letters – We need to apply some transformation to the input before we test is. So we’ll first remove spaces from the input, and then test to see if the result is a palindrome. That way, the space between “taco” and “cat” will have no effect on our result, because we will have removed it.
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
(:). 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.
- 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.
- 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
withoutSpacesfunction to just the
- 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
withoutSpacesrecursively 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.
madam, I’m adam!
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.
filter :: (Char -> Bool) -> String -> String
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.
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.
firstis something we want to keep, so after we recursively apply
myFilter predicateto the
remainder, we will cons
firstback onto the result so that we keep that character.
False, then we only return the result from filtering the
filter function in
Prelude is more general than the one we’ve defined here.API documentation for
λ> :type filterfilter :: (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
Char, we get the same type as
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.
filter even [1,2,3,4]
In this first incarnation of the list, the head is
1, and the tail is
filter even (1 : [2,3,4])
Since the predicate
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,
filter even (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,
2 : filter even (3 : )
3 is discarded, and we are left with
4 as the first item, and
 as the remainder.
2 : filter even (4 : )
4 is even.
2 : 4 : filter even 
Any time when we filter an empty list, we get an empty list. So the final application reduces to
2 : 4 : 
Written in the more concise list notation, this ultimate result is the list
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
not False is
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.
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.