Please Buy now at Leanpub
Written and illustrated by GetContented.
Published on 2017-07-08.
We’re going to use Haskell to make a shopping list for when we go to shop for food, and to write some code to find out how many items we have on it.
Before we make the list, let’s see how to make the simplest list possible in Haskell, calling it aList:
aList = []
We’ll get to the types in a minute, but this is a definition for a name called aList and it’s defined to be the empty list. This is the name given to those square brackets on the right with nothing between them: it’s a list that has nothing inside it.
What about a list with one thing inside it? Let’s say we want to have a list with “sauce” written in it. Well, there are two main ways to do that. First up, we could build it up using the (:) operator:
aList2 = "sauce" : []
This might look a bit weird, but the (:) operator is just a function that makes new bigger lists out of old ones. It’s an infix function and like all operators, it takes two arguments: in this case, an element ("sauce") and a list ([]). Remember that infix means it sits in between its arguments? What (:) does is make a new list with the element argument prepended to the list argument. That is, it returns a fresh list with the element at the front of the list.
It’s important to notice that "sauce" : [] doesn't do anything to the [] value. It’s still the empty list, and it doesn’t change when we write expressions that use it. The aList2 definition and expression just uses it, but it doesn’t change it.
Because (:) is an operator, we can also apply it as if it were a prefix function, by using parentheses:
-- a list with just pie on it
aList3 = (:) "pie" []
This is the same thing as aList2, but with "pie" instead of "sauce". It’s a different syntax, though. Syntax is the form of writing something. If we use parentheses around an operator, it works like a regular prefix function of two arguments.
There’s yet another way to make a list, which is the most usual way that you’ll see in Haskell programs:
-- a list with just napkin on it
aList4 = ["napkin"]
You need to recognise these three ways a list can be written, but we’ll give you lots of practice, so don’t worry!
So what’s the type of aList4? Let’s see:
aList4 :: [String]
aList4 = ["napkin"]
Ok so, usefully, its type looks very similar to how we write its values!
There is another way to write this type (it’s a bit of a strange way to write it, though), so let’s quickly see that here:
aList4 :: [] String
aList4 = ["napkin"]
We can put the type name (the brackets) on the left, or wrapped around the second type.
So, because it “takes another type” as an argument similarly to a function, we can call the list type a kind of container type: it has two pieces - the container type (List), and its element type in the case of List (in the above, it’s String). That is, the list type is a parameterised type.
There are many container types in Haskell, and almost none of them besides this one have this “wrap-around-another-type” syntax. This can sometimes confuse people when they get to learning the other container types, which is why we’re introducing the normal syntax now.
Just know that even though list has a special syntax, it's still a regular data type, which is why we can write the string list type using regular type syntax as [] String as well as the special list syntax of [String].
So, moving on... what would a list with an Integer value in it look like?
aList5 :: [Integer]
aList5 = [879]
Ok. So by now you’ve probably noticed how using the list type is sort of similar to function application, but for types rather than values.
A function is a thing that "wraps" another value to turn it into another value. The function (+5) for example, wraps a number to turn it into a number 5 greater than the first one: we do this by applying the function to the value.
Well, these “container types” like list, they actually take a variable, too! This is obviously not like the value variables that functions take, though, it's a type variable! This means in a type signature, you put another type with it as we’ve seen, which will result in a composed type. In the case of list, the parameter is the type of its elements. By itself, List doesn’t actually mean anything other than the potential for a list-like type of some variety.
That is, by itself, in the same way that functions don’t result in a concrete value until you apply them to another value, types with type variables are not a concrete type until you put a type with them.
By the way, we can, of course, write the above code using the (:) data-constructor operator instead. The following means the exact same thing:
aList6 :: [Integer]
aList6 = 879 : []
So this is great and all, but we want to write a whole shopping list, not just a list with one item on it! We’re going to need more items.
Here’s a definition for a list with two items:
aList7 :: Num a => [a]
aList7 = [1,3]
We notice two things here. First, to have more items you put commas between items in this syntax. Second, we notice that we haven’t told Haskell a concrete type for our list. It’s a Num-constrained value called “a”!
This means that we’re letting Haskell work out what type the numbers are. All we care about is that the type that Haskell picks for them is an instance of the Num typeclass. This is not to say that they don’t have an actual type when Haskell compiles our code, it definitely will.
These kinds of values with typeclass-constrained types, like the type Num a => a, are called polymorphic values. Polymorphic just means many-shaped, and comes to us from Greek. The empty list ([]) is actually a polymorphic value, too. That’s how we’re able to write "sauce" : [] or 1 : [] and have Haskell still match the types properly:
-- the type of the empty list.
-- "t" could be any variable name
[] :: [t]
So the empty list is a value, which from looking at its type signature, can see we use any type we like with it. When we hook it up to a value with a more concrete type like Integer, say, Haskell infers we must mean the empty list of Integer, because nothing else would make sense ( [] :: [Integer]).
Interestingly, the List type is a polymorphic type. That means it takes an argument, which will be another type! We just saw this a few times when we saw Lists of String ([String]), and Lists of Integer ([Integer]), and just now a List of Num a => a when we saw aList7 = [1,3] :: Num a => [a].
Okay, so here’s another definition for this same list, constructed using the (:) operator:
aList8 :: Num a => [a]
aList8 = 1 : 3 : []
There's nothing much new here, except that if you’ve got a mind like a super keen blade, you’ll have noticed something odd about the (:) operator, which is in order for this code to work, Haskell must be applying the (:) function to 3 and [] first, otherwise it would be applying it to 1 and 3, which we know is impossible because of the type of (:) :: a -> [a] -> [a] — its second argument has to be a list.
So what’s going on here, then? The (:) operator is binding to the right; it has what’s called right-associativity. Binding can be described as when you apply a function to a value or variable, you’re binding the value as the function’s argument. Associativity is just a fancy name meaning “the order functions evaluate their arguments in when there are no parentheses around”.
The (:) operator usually functions as though it were written like this:
-- we don't need these parentheses
aList8 :: Num a => [a]
aList8 = 1 : (3 : [])
Interesting! Most functions we’ve seen so far bind to the left (they’re left-associative). So this one is right-associative, in other words, it prefers to associate to the things to the right of it first before it gets to the left. So Haskell looks at the 1, then looks at the first (:) and says “hey, let’s wait until we’ve seen what’s more to the right of this (:) before we do any binding or application here”.
It’s good that it’s set up like this, because if it were left-associative, then it would try to do (1 : 3) first, which would not work because (:) takes an element and a list as arguments, and 3 is not a list. In that case, we’d have to write lots of parentheses to get it to work properly, which would be a pain.
Again, here’s the type of the (:) operator:
(:) :: a -> [a] -> [a]
This means it’s a function that takes any value at all of some type called “a”, and a list of that same “a” type, and returns another list of that type.
We’ve covered a lot so far, so let’s just take a look at the shopping list program that prints a shopping list on the screen while we catch our breath.
shoppingList :: [String]
shoppingList =
[ "Carrots"
, "Oats"
, "Butter"
, "Apples"
, "Milk"
, "Cereal"
, "Chocolate"
, "Bananas"
, "Broccoli"
]
main :: IO ()
main = print shoppingList
This program just prints the shopping list data using print, which uses the built in Show instance for List and prints a list on the screen in the usual program notation above. It's not very pretty!
How do we know it uses show to print this out? Well the print function takes a value whose type has a Show instance, remember? Let’s remember its type: print :: Show a => a -> IO ().
What if we want to print out the number of items on the list instead? Well there’s a function called length that will give us just that:
length :: Foldable t => t a -> Int
This type signature looks kind of crazy because the function is extremely general — that is, it works with values from a whole class of container types! Let’s break it down.
We recognise there is a type constraint Foldable t =>, but that it’s using a typeclass that is new for us called Foldable. This is specified on the type variable “t”. Then there’s a type variable “a”, which is completely unconstrained, so it can be anything we like.
This “t a” might feel a little bit familiar, because it’s a generalised version of what we’ve just seen when we arrange our list’s type in that odd way we discussed: ["hey"] :: [] String. Let’s see, does this look similar?
aList9 :: [] String
aList9 = ["Cat Food", "Lasagne"]
What about if we told you that list is an instance of the Foldable typeclass? Well, it is. So, the type [] String could match Foldable t => t String.
So, thinking about the length function again, it takes a single value. The type of that value is “t a” where “t” is a wrappering type around “a”, and where t is constrained to types that are Foldable.
Foldable is a class of types that have a shape or structure that lets us reduce them to a single value in various ways. The length function reduces a Foldable structure down to a single Int value representing the item count of the “container of items”. You can see why it’s called Foldable if you think of cooking where you fold eggs into batter — you might fold three eggs, say, into one single batter mix.
The fact that the list type has an instance specified for Foldable means it can be the “t” in our type signature for Foldable t => t a. We know from the above that when we write the type [String], it means the same as the type [] String.
If this is at all confusing, well don’t worry about it too much for now. We’ll see many more examples of types that are composed of two or more parts like this later on.
So, we can safely pass length our shoppingList, because the types will match. It will happily return the number of items in it as an Int value.
Let’s adjust our program so it prints a nice message with the number of items in our shopping list:
shoppingList :: [String]
shoppingList =
[ "Carrots"
, "Oats"
, "Butter"
, "Apples"
, "Milk"
, "Cereal"
, "Chocolate"
, "Bananas"
, "Broccoli"
]
main :: IO ()
main = putStrLn ("There are "
++ (show (length shoppingList))
++ " items on the shopping list.")
Wow, that is a lot of parentheses. Later we’ll see how to reduce the number of parentheses used. Also, what is this new operator (++)?
Well, (++) joins, or concatenates, two lists together. Happily for us, the String type is itself just a list of type Char (the type of all written characters). That is, String is identical to [Char]. The type of (++) is [a] -> [a] -> [a], so here we’re just joining three strings together to print out.
Now, let’s look at another way to represent shoppingList (which Haskell sees as identical to the above):
shoppingList :: [String]
shoppingList =
"Carrots" :
"Oats" :
"Butter" :
"Apples" :
"Milk" :
"Cereal" :
"Chocolate" :
"Bananas" :
"Broccoli" : []
This shouldn’t pose too much of a problem by now. As we know, the (:) operator has type a -> [a] -> [a], which means it takes a single item of any type, and a list of items of that same type, and then returns a list of items with that same type.
We can do like the above; chain the function applications of (:) to make a list, as long as we put a list of some kind at the end.
The (:) operator is very handy. Because it’s a value constructor, we can also use it in pattern-matching to match parts of lists in arguments to functions! This is the case for all value constructors.
Let’s take a look at a function that will get the first item from any list of strings (which includes our shoppingList obviously, because it’s just a list of strings). If the list is empty, it’ll just return a blank String:
firstOrEmpty :: [String] -> String
firstOrEmpty [] = ""
firstOrEmpty (x:_) = x
Remember when pattern-matching, the definitions or patterns that appear earlier in the list will get their arguments matched first, if they can.
The first definition for this function is very easy to understand. It just matches on the empty list, which if it finds it, it returns the empty String. We have this in case an empty list is passed in as its argument. If we left it out and an empty list was passed, it would cause a runtime error when we ran our program. This would be bad. Including it makes the function total, which means it covers all possible values.
It’s good to have total functions because programs change, and when they do, unexpected things can happen. Total functions let us stop some of those unexpected things happening, and so we can find any errors when the program is being compiled (called compile-time) rather than when it’s being executed (called run-time).
The second definition is using the (:) value constructor operator as a pattern matcher. We know this value that we’re pattern matching on must be a list with at least one item on it, because to get to the second definition, the first “empty list match” must have been passed over (we can say that it failed matching).
So, the (:) operator “pulls” the first item of the list out and “puts” it into the variable x, and then the “_” part throws the remainder of the list away, and this part of the function just returns the first item of the list as its result! This is pretty neat, isn’t it?
So, does this mean we can pattern match with any function inside arguments like this? No. The (:) operator is actually part of the list type, and is used as we know, for constructing values. We’ve seen this happen when we write expressions like 1 : 2 : []. We’re using it there to build up a list. These functions are called data constructors, or value constructors. We can use them when in patterns for pattern matching, but we can’t use ordinary functions, so don’t expect to see (+) in a pattern match any time soon!
We know this will be a little hazy for you right now, but it will become clearer as we start to learn about more complicated data types later on. Don’t worry too much about this for now.
You know that (:) is an operator, and operators can be changed from infix functions to prefix functions by using parentheses. Let’s see what happens when we try to match using the (:) as a prefix function:
firstOrEmpty' :: [String] -> String
firstOrEmpty' [] = ""
firstOrEmpty' ((:) x _) = x
Haskell has no problem with this at all, and nor should it. It turns out ((:) x _) as a pattern means exactly the same thing as (x:_). You probably won’t see this very much in any source code you encounter, because it’s less easy to read and write, but we’re showing you here so that you understand that (:) is not syntax or special, it’s just a data-constructor function, and they can all be used in patterns in the same way.
Let’s see another function. This takes the first two elements of a String list and joins them together with a comma if there are at least two items in the list, otherwise it just returns the first one if there’s one, otherwise an empty String.
firstOnesOrEmpty :: [String] -> String
firstOnesOrEmpty [] = ""
firstOnesOrEmpty [x] = x
firstOnesOrEmpty (x:y:_) = x ++ ", " ++ y
Fancy, right? You can use more than one (:) in your pattern matches. Notice in order to make sure our function was total, we had to add another definition. [x] matches only lists with exactly one item in them, and returns the single String inside. So you can use either the (:) value constructor, or the special [] syntax to pattern match variables out of lists. So we could rewrite the firstOnesOrEmpty [x] = x clause as firstOnesOrEmpty (x:[]) = x and it’d mean the exact same thing.
Now, we’re going to blow your mind a little bit. Don’t worry if this confuses you. Just read it carefully, and it might make sense. We’ll cover this a lot more, so if it doesn’t then that’s fine.
What if we wanted something that would put comma-space between all of the elements of the list of strings and join them into one single string? Let’s take a look:
joinedWithCommas :: [String] -> String
joinedWithCommas [] = ""
joinedWithCommas [x] = x
joinedWithCommas (x:xs) = x ++ ", " ++ joinedWithCommas xs
Notice the last definition actually refers to itself! This is called recursion. We’ve stopped using “_” to “throw away” the rest of the list, we pattern-match it into a variable called xs, and then we use it... by passing it back into an application of the very same function we’re defining!
What? Crazy! Completely cool, though! Recursion is an incredibly common and useful thing in Haskell.
This function is actually already implemented more generally in a Module called Data.List as the function named intercalate. We’ll see it later when we use that module. It’s more general because you can put anything between the items, not just ", " as we have here.
So our final program below prints out the count of items, and then the whole comma-separated list.
shoppingList :: [String]
shoppingList =
[ "Carrots"
, "Oats"
, "Butter"
, "Apples"
, "Milk"
, "Cereal"
, "Chocolate"
, "Bananas"
, "Broccoli"
]
main :: IO ()
main = putStrLn ("There are "
++ (show (length shoppingList))
++ " items on the shopping list."
++ " and the list is: "
++ joinedWithCommas shoppingList)
joinedWithCommas :: [String] -> String
joinedWithCommas [] = ""
joinedWithCommas [x] = x
joinedWithCommas (x:xs) = x ++ ", " ++ joinedWithCommas xs
Your homework is to think about this recursive function, think it through, and also to run all the code.
Think about what joinedWithCommas would do if it was passed an empty list, and one String, then two Strings, what would it do for three?
We’ll explain it more soon, so if you don’t understand it yet, it’s to be expected and don’t worry about it. This can take many months to understand properly.
If you’ve enjoyed reading this, please consider purchasing a copy at Leanpub today
Please follow us, and check out our videos Follow @HappyLearnTutes
Also, Volume 2 is now in beta and being written! Show your support and register your interest at its Leanpub site.