- 21 minutes
In this session we’ll review what we’ve done, reorganize the code, and then join together the separate parts into one unified program.
Quick recap of palindrome things we’ve done so far:
- First we wrote
isPalindrome, the basic palindome test:
word == reverse wordtells us whether a word is spelled the same forward and backward.
- We wrote a
mainaction to turn our function into an interactive program that somebody could execute and use.
We also made some improvements to the basic palindrome test.
nonemptyPalfunction rejects empty inputs, because if you haven’t typed anything at all, then that’s not really a palindrome.
verbosefunction returns a nice output message instead of just printing “True” or “False”.
isPalindromeIgnoringCasefunction ignores capitalization, so that we can capitalize the first letter in a word and still have it count as a palindrome.
isPalindromePhrasefunction 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:
import Data.Char isPalindrome :: String -> Bool isPalindrome word = word == reverse word nonemptyPal :: String -> Maybe Bool nonemptyPal word = case word of  -> Nothing _ -> Just (isPalindrome word) main :: IO () main = do word <- getLine print (verbose word) verbose :: String -> String verbose word = case (nonemptyPal word) of Nothing -> "Please enter a word." Just False -> "Sorry, this word is not a palindrome." Just True -> "Congratulations, this word is a palindrome!" myHead :: [a] -> a myHead (first:rest) = first myTail :: [a] -> [a] myTail xs = case xs of  ->  (first : rest) -> rest allLowerCase :: String -> String allLowerCase word = myMap toLower word allLower :: String -> String allLower = myMap toLower myMap :: (a -> b) -> [a] -> [b] myMap func list = case list of  ->  first : remainder -> func first : myMap func remainder isPalindromeIgnoringCase :: String -> Bool isPalindromeIgnoringCase word = isPalindrome (allLowerCase word) isPalindromePhrase :: String -> Bool isPalindromePhrase phrase = isPalindrome (myFilter notSpace phrase) withoutSpaces :: String -> String withoutSpaces phrase = case phrase of  ->  ' ' : remainder -> withoutSpaces remainder first : remainder -> first : withoutSpaces remainder myFilter :: (Char -> Bool) -> String -> String myFilter predicate string = case string of  ->  first : remainder -> if (predicate first) then (first : myFilter predicate remainder) else (myFilter predicate remainder) notSpace :: Char -> Bool notSpace x = not (x == ' ') notPunctuation :: Char -> Bool notPunctuation x = not (isPunctuation x)
The first thing we can do is remove some things.
We wrote some functions for practice that can be replaced by
myMapcan be replaced with
myFiltercan be replaced with
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.
= myMap toLower wordallLowerCase word
= map toLower wordallLowerCase word
: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
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
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:
- The part of the code that deals with defining what a palindrome is and how to test it;
- 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
verbose into their own section of the file and labelling the two sections with a comment.
The file now looks like this:
import Data.Char -- The interactive program -- main :: IO () main = do word <- getLine print (verbose word) verbose :: String -> String verbose word = case (nonemptyPal word) of Nothing -> "Please enter a word." Just False -> "Sorry, this word is not a palindrome." Just True -> "Congratulations, this word is a palindrome!" -- What a palindrome is -- isPalindrome :: String -> Bool isPalindrome word = word == reverse word nonemptyPal :: String -> Maybe Bool nonemptyPal word = case word of  -> Nothing _ -> Just (isPalindrome word) allLowerCase :: String -> String allLowerCase word = map toLower word isPalindromeIgnoringCase :: String -> Bool isPalindromeIgnoringCase word = isPalindrome (allLowerCase word) isPalindromePhrase :: String -> Bool isPalindromePhrase phrase = isPalindrome (filter notSpace phrase) notSpace :: Char -> Bool notSpace x = not (x == ' ') notPunctuation :: Char -> Bool notPunctuation x = not (isPunctuation x)
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.
isPalindrome :: String -> Bool = isPalindrome word == reverse word word
isOwnReverse :: String -> Bool = isOwnReverse word == reverse word word
Then, each place
isPalindrome appears is used elsewhere in the code, we must replace it with the new name,
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
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
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
Also move the
import Data.Char line from
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.
Pal.hs file should look like this:
module Pal where import Data.Char isPalindrome :: String -> Maybe Bool isPalindrome = undefined isOwnReverse :: String -> Bool isOwnReverse word = word == reverse word nonemptyPal :: String -> Maybe Bool nonemptyPal word = case word of  -> Nothing _ -> Just (isOwnReverse word) allLowerCase :: String -> String allLowerCase word = map toLower word isPalindromeIgnoringCase :: String -> Bool isPalindromeIgnoringCase word = isOwnReverse (allLowerCase word) isPalindromePhrase :: String -> Bool isPalindromePhrase phrase = isOwnReverse (filter notSpace phrase) notSpace :: Char -> Bool notSpace x = not (x == ' ') notPunctuation :: Char -> Bool notPunctuation x = not (isPunctuation x)
Then go back to
main.hs and add
import Pal at the top of the file. This imports all of the definitions in the
nonemptyPal, etc. and makes them all available for use within the
main.hs file should now look like this:
import Pal -- The interactive program -- main :: IO () main = do word <- getLine print (verbose word) verbose :: String -> String verbose word = case (isPalindrome word) of Nothing -> "Please enter a word." Just False -> "Sorry, this word is not a palindrome." Just True -> "Congratulations, this word is a palindrome!"
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:
import Pal (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.
- Normalization – the removal of extraneous characters from the input – e.g. the transformation of “Madam, I’m Adam!” into “madamimadam”.
- Rejection of empty inputs – the transformation of
- The basic test to see whether a string is its own reverse –
"cat"is not, but
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
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.
Pal.hs:8:37: error: • Couldn't match expected type ‘Maybe String’ with actual type ‘[Char]’ Expected type: String Actual type: Maybe String • In the first argument of ‘isOwnReverse’
The problem, it says, is the argument to
- The expected type is
String, because this is the input type for the
isOwnReversefunction. The function type is
String -> Bool, so the argument should always be a
- The actual type – the type of the expression that we have used at the argument to
Maybe String. This is because the type of the
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
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
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.
An input of
Nothingsignifies that the input had been rejected, so we want to return
Nothinghere for the final output as well, since the input is still rejected.
If we do have a string input, then we want to apply
isOwnReverseto that string. We need a
Maybe Boolresult, and
isOwnReversegives us a
Bool, so we have to wrap that up in a
Justconstructor to give it the right type.
Reload to confirm that this code loads successfully. Then let’s go back and finish implementing
rejectEmpty is going to be similar to
nonemptyPal. As a reminder, this is what the
nonemptyPal looks like:
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
normalize function that removes unwanted details from the input.
Again, we can find that this decomposes into a series of three steps.
- Remove spaces (“taco cat” → “tacocat”)
- Remove punctuation (“Hip, hip, hooray!” → “Hip hip hooray”)
- 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!"
The dot operator
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:
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:
(.) :: (b -> c) -> (a -> b) -> a -> c .) f g x = f (g x)(
Here’s how we wrote the code above:
= normalize string filter notPunctuation (filter notSpace (allLowerCase string)) = isPalindrome string isOwnReverse (rejectEmpty (normalize string))
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:
= normalize filter notPunctuation . filter notSpace . allLowerCase = isPalindrome . rejectEmpty . normalize isOwnReverse
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).