# Removing spaces

Video
• 14 minutes

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.

## Space removal

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.

``````isPalindromePhrase :: String -> Bool
isPalindromePhrase phrase =``````

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.

``````isPalindromePhrase :: String -> Bool
isPalindromePhrase phrase =
isPalindrome (withoutSpaces phrase)

withoutSpaces :: String -> String
withoutSpaces phrase = ...``````

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.

``````withoutSpaces :: String -> String
withoutSpaces phrase =
case phrase of
[] ->
first : remainder ->``````

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.

``````withoutSpaces :: String -> String
withoutSpaces phrase =
case phrase of
[] ->                      -- 1
' ' : remainder ->         -- 2
first : remainder ->       -- 3``````
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.
``````withoutSpaces :: String -> String
withoutSpaces phrase =
case phrase of
[] -> []
' ' : remainder -> withoutSpaces remainder
first : remainder -> first : withoutSpaces remainder``````

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

``````λ> withoutSpaces "taco cat"
"tacocat"

λ> isPalindrome "taco cat"
False

λ> isPalindromePhrase "taco cat"
True``````

## Other troublemakers

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.

``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 :: (Char -> Bool) -> String -> String
myFilter predicate string =``````

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.

``````myFilter :: (Char -> Bool) -> String -> String
myFilter predicate string =
case string of
[] -> []
first : remainder ->``````

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.

``````myFilter :: (Char -> Bool) -> String -> String
myFilter predicate string =
case string of
[] -> []
first : remainder ->
if (predicate first)
then (first : myFilter predicate remainder)  -- 1
else (myFilter predicate remainder)          -- 2``````
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`.

## Filter

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

``````λ> :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 `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 `[2,3,4]`.

``filter even (1 : [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]`.

``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, `[3,4]`.

``2 : filter even (3 : [4])``

`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 `[2, 4]`.

## Using filter

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`.

``````withoutSpaces :: String -> String
withoutSpaces phrase = myFilter notSpace phrase

notSpace :: Char -> Bool
notSpace x = not (x == ' ')``````

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.

``````isPalindromePhrase :: String -> Bool
isPalindromePhrase phrase =
isPalindrome (myFilter notSpace phrase)``````

## Exercise

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.

Join Type Classes for courses and projects to get you started and make you an expert in FP with Haskell.