Composition

Quick recap of palindrome things we’ve done so far:

• First we wrote isPalindrome, the basic palindome test: word == reverse word tells us whether a word is spelled the same forward and backward.
• We wrote a main action to turn our function into an interactive program that somebody could execute and use.

We also made some improvements to the basic palindrome test.

• The nonemptyPal function rejects empty inputs, because if you haven’t typed anything at all, then that’s not really a palindrome.
• The verbose function returns a nice output message instead of just printing “True” or “False”.
• The isPalindromeIgnoringCase function ignores capitalization, so that we can capitalize the first letter in a word and still have it count as a palindrome.
• The isPalindromePhrase function ignores spaces and punctuation, so that we can write “taco cat” as two words.

Some of these improvements we made separately, though - We never got around to writing one big program that has all of these features. So, what we’re going to do right now is bring them all together into one bigger program that does everything.

Before we get to that, though, we really need to spend some time on cleanup and organization. This is getting to be way too much code, and a bit of tidiness would go a long to help us keep track of what we have, what’s where, and what we still need to do. This code could really benefit from some refactoring.

Here is what our main.hs file currently looks like:

The first thing we can do is remove some things.

We wrote some functions for practice that can be replaced by Prelude functions:

• myMap can be replaced with map.
• myFilter can be replaced with filter.

Start by finding every place where myMap appears in the code (other than the definition of myMap), and change each occurrence to map. Do not delete the myMap function yet.

Before:

After:

Save main.hs and :reload it in GHCi. When you refactor, try to work in small steps, and reload after each step to make sure that all of the code still compiles. When reloading succeeds, this confirms that we were correct in our understanding that map is a suitable replacement for our myMap function.

Now that we are no longer using myMap, remove its definition. Reload after this step as well, to confirm that all of the usages of myMap have been elimated. If the reload fails, you may have mistakenly missed one of the replacements in the previous step. If it succeeds, then you have gotten them all.

Do the same thing with myFilter.

The myHead and myTail functions can also be removed; we only wrote them for practice, and we never used them. Remove these two definitions, and :reload to confirm that we were not using them.

We can also remove withoutSpaces, because the isPalindromePhrase function now uses filter notSpace instead.

allLower is the same as allLowerCase – we had written two versions of the same function to demonstrate two different ways to write it. Remove allLower, which is the one we aren’t using.

We’ve said that the order of definitions within a file doesn’t matter at all – this is true, to the compiler. But it does matter a lot to us. If affects the order in which we read it. We can use ordering and comments to communicate to readers and to ourselves which definitions are most closely related to each other.

This program’s definitions can be separated pretty cleanly into two distinct categories:

1. The part of the code that deals with defining what a palindrome is and how to test it;
2. The interactivity, how we should prompt the user for a message, and how we display the results back to the user.

The organization could perhaps be improved, then, by moving the main and verbose into their own section of the file and labelling the two sections with a comment.

The file now looks like this:

The best way to divide up code into sections is, of course, a subjective judgement. But there’s a couple reasons why we believe this grouping is a good one.

The “what a palindrome is” code is all pure functions, and the interactive program involves IO. A lot of programs end up being separable in this way, into an I/O portion that deals with the program’s “behavior” and a pure portion that deals with its “logic”.

There is a further difference between these two parts of the code beyond the superficial observation that an IO type appears in the one section and not in the other: We suspect it is very likely that the times and reasons we might want to update the code in one section or the other are pretty distinct.

• Once we’ve settled on a definition of what a palindrome is, for instance, maybe we’re never going to need to change that code anymore – and it can just stay there, untouched, indefinitely – and we can remove it from our minds while we spend the rest of our time fiddling with the details of how the interactivity should work and how the messages should be displayed.
• Or, if we do want to rethink the logic and redefine what it means for something to be a palindrome, then we know where to go: we’ll need to edit the code in the “what a palindrome is” section, and we can be fairly confident that we won’t have to deal with the “interactive program” section to make the change.

We do not want to dwell more than necessary on finding the perfect name for everything, but there is one change of name that may be particularly helpful in this code, because the present name is misleading.

We called this function “isPalindrome” because it was our first attempt at defining what a palindrome is. We subsequently changed our mind about what exactly a palindrome is when we decided that this simple test wasn’t good enough – but the function called “isPalindrome” is still this old insufficient one.

Now, we don’t want to get rid of this function, because we use it in several places, and still serves a purpose. But what we can do is rename this function to something that better describes what it actually does. Then we can free up the “isPalindrome” name to be the name of what we end up assembling at the end, our most complete definition of what we think constitutes a palindrome.

So, what does this function really do? It doesn’t tell us if a string is a palindrome – it tells us if a string is its own reverse. So “isOwnReverse” seems like a fine name.

Before:

After:

Then, each place isPalindrome appears is used elsewhere in the code, we must replace it with the new name, isOwnReverse.

What’s nice about the separation of this module into two sections is that we can then start thinking about the relationship between the two sections – What are the points where they interact with each other?

We need only one point of interaction between the sections. This is the function that we want to call isPalindrome.

This will be the function that we haven’t written yet that combines all of the features that we wrote in the previous lessons. isPalindrome is going to constitute the entire relationship between the interactive program and the definition of palindromes.

Modify the definition of verbose so that it uses this yet-to-be-defined isPalindrome function:

Of all the definitions in the “what a palindrome is” section, isPalindrome is the only one that will appear in the “interactive program” section.

To fully convince ourselves of this fact, and to make the division between the two sections of code apparent to anyone who is reading our code in the future, we can take all of this palindrome code in the second section and split it off into a different module.

We’re going to call this module Pal (short for ‘palindrome’). Create a new file called Pal.hs. Begin this file as follows:The file name should match the module name, including the capitalization of the letter P. Strictly speaking, the file name does not have to match the module name, but doing so is helpful because it allows GHCi to find the file automatically.

This opening line is how we specify that the name of the module defined by this file is Pal. We did not have a line like this in main.hs because when you omit the module line, the name of the module defaults to Main, which is what we wanted in that case. When you want to write a module whose name is anything other than Main, you need to include this module ... where bit at the top.

Move the entire “what a palindrome” section from main.hs into Pal.hs.

Also move the import Data.Char line from main.hs to Pal.hs, because the code that uses functions from Data.Char is now in the Pal module.In the video, you can see what happens when we accidentally forget to move the import. Whenever we move code between files, we have to make sure we also copy or move any relevant import statements.

The new Pal.hs file should look like this:

Then go back to main.hs and add import Pal at the top of the file. This imports all of the definitions in the Pal module: isPalindrome, isOwnReverse, nonemptyPal, etc. and makes them all available for use within the Main module.

The main.hs file should now look like this:

At this point, if you :reload in GHCi, both modules should load successfully.

There is one interesting tweak that we can make at the place where main.hs imports the Pal module. Here’s what it looks like now:

And we said that this imports the entire Pal module. But isPalindrome is the only function from Pal that we actually need in main.hs. So we can assert that in the code. In parentheses at the end of the import line, we may list the specific things that we want to import. In this case, only one thing: isPalindrome.

If that compiles successfully (it does), that confirms our suspicion that isPalindrome is the one link between these two modules.

We have no further changes to make to the interactive portion of this program, so can close main.hs and focus our attention solely on what we’ve moved into Pal.hs. We are now left with the slightly smaller problem of bringing together all of our different thoughts about the true definition of a palindrome.

Back away from the code we’ve written for a moment and think in the abstract about what we’ve decided. There are three main steps that we need to put together:Notice that the order of the three steps matters. We need to do the normalization before rejecting empty inputs, for example, because if the input is a string consisting entirely of spaces, then the normalization process will turn that into an empty input which should subsequently be rejected by step two.

1. Normalization – the removal of extraneous characters from the input – e.g. the transformation of “Madam, I’m Adam!” into “madamimadam”.
2. Rejection of empty inputs – the transformation of "" into Nothing and e.g. "cat" into Just "cat".
3. The basic test to see whether a string is its own reverse – "cat" is not, but "tacocat" is.

The output from step 1 needs to be the input to step 2. The output from step 2, in turn, needs to be the input to step 3. It is very nice when a problem decomposes in this way! Sometimes we describe this as a “pipeline” of steps, a chain of things that we need to do one after another.

We can write this as a chain of three nested function applications.

isOwnReverse is already written, but we’ll still need to write the other two functions.

Before we go ahead and write real definitions for rejectEmpty and normalize, we should :reload in GHCi to verify that the concept we’ve outlined above passes the type checker.

It does not! There are two error messages; we will focus on the second one.

The problem, it says, is the argument to isOwnReverse.

• The expected type is String, because this is the input type for the isOwnReverse function. The function type is String -> Bool, so the argument should always be a String.
• The actual type – the type of the expression that we have used at the argument to isOwnReverse – is Maybe String. This is because the type of the rejectEmpty function is String -> Maybe String.

So, what do we need to do?

For step 3, what we really need is not a String -> Bool function, but a function that can accept a Maybe String and return a Maybe Bool.

If we then use isOwnReverseMaybe instead of isOwnReverse, then this will work out.

So now let’s write isOwnReverseMaybe. As usual, we can start by writing a case expression that lists the two cases of Maybe: Nothing and Just.

Now think about what the results for each case should be:If you find something dissatisfying about having to write this isOwnReverseMaybe function, do not despair; we will get to the more concise approach a few lessons from now.

1. An input of Nothing signifies that the input had been rejected, so we want to return Nothing here for the final output as well, since the input is still rejected.

2. If we do have a string input, then we want to apply isOwnReverse to that string. We need a Maybe Bool result, and isOwnReverse gives us a Bool, so we have to wrap that up in a Just constructor to give it the right type.

Reload to confirm that this code loads successfully. Then let’s go back and finish implementing rejectEmpty and normalize.

rejectEmpty is going to be similar to nonemptyPal. As a reminder, this is what the nonemptyPal looks like:

The rejectEmpty function is just going to do a bit less.

The only difference is that we didn’t apply isOwnReverse to the word this time, because we’ve deferred that part to step 3 in the pipeline (1. normalize; 2. rejectEmpty; 3. isOwnReverse). Expressing the palindrome test as the composition of three separate steps allows each of the three constituent functions do perform a smaller job.

We may now eliminate the nonemptyPal function.

Next, the normalize function that removes unwanted details from the input.

Again, we can find that this decomposes into a series of three steps.

1. Remove spaces (“taco cat” → “tacocat”)
2. Remove punctuation (“Hip, hip, hooray!” → “Hip hip hooray”)
3. Convert to lower case (“Cat” → “cat”)

In this case, it so happens that the order in which we perform these steps doesn’t matter at all. Each of the three is a String -> String function, and the result will be the same no matter what order we compose them in.

Now we’re done! Try it out with an input that hits all of our potential pitfalls.

λ> main
Madam, I'm Adam!
"Congratulations, this word is a palindrome!"

When programmers speak of “composition”, in the most general sense we are describing any means of combining multiple things into one bigger thing. We are often more specifically referring to combining things of the same type to produce another value of that type. For example: Combinining some functions to produce a function that applies them all one after the other. We’ve now seen two definitions like this: isPalindrome and normalize.

We often like to write definitions like this using the (.) operator.API documentation for (.) This is a small function in Prelude that produces the composition of two functions. Its definition looks like this:

Here’s how we wrote the code above:

And here’s what it looks likeEach of our examples here uses the (.) operator twice, because there are three functions to join together, not just two. written using the function composition operator:

The difference is only aesthetic; we sometimes prefer to use (.) because it is slightly more concise, and because it saves us from the small burden of choosing a name for the parameter (notice that the string parameter disappears in the revised code).