Please Buy now at Leanpub
Written and illustrated by GetContented.
Published on 2016-08-14.
Let’s take a look at a program which will let us work out how much our shopping list will cost in total.
To do this, we’ll use a new type of data called a Tuple. A Tuple lets you keep some number of items of potentially different types together as one item. We can have 2-tuples, 3-tuples, and so on.
aShoppingListItem :: (String, Int) aShoppingListItem = ("Bananas", 300)
This is a single shopping list item: a 2-tuple value. It has the
String "Bananas", and the
Int 300 which we’re going to use to represent the number of cents that the bananas cost.
We can have tuples of different lengths. There are 3-tuples, and 4-tuples, and you can pretty much have as many as you’d like but it’s best to just stick to two, or maybe three at the very most. There are better ways to build up composed data types that we’ll see later on if you need to do that.
In the same way as we know that
[String] is a type that can be expressed as
 String, we can express the 2-tuple
(String, Int) as
(,) String Int. In the same way, the 3-tuple
(Int, String, Int) could be expressed as
(,,) Int String Int, and so on. You can see the pattern. Note that each of the composed types can be any type at all. So, tuple types are created with the
(,) style type constructors, there is actually an identically named value constructor for tuples. So you could just as easily write your tuple values as
("Bananas", 300), or as
(,) "Bananas" 300.
We actually want a list of these items, though. Let’s take a look what it’d look like to have a new name for our
(String, Int) tuple type so our program is more self-explanatory.
type ShoppingListItem = (String, Int) aShoppingListItem :: ShoppingListItem aShoppingListItem = ("Bananas", 300)
We use “
"type"” to tell Haskell we’re defining a type alias (or type synonym). This means Haskell sees
ShippingListItem as being the same type as
(String, Int). This is just to make our programs more readable for us. Haskell won’t see these types as different, so if you accidentally used a
(String, Int) where you meant to use a
ShoppingListItem, then Haskell won’t complain. Ideally, we’d like it to, though.
Note that in Haskell, all types must start with a capital letter, and all variable names must start with a lowercase letter.
Ok so let’s look at another couple of type synonyms to make things clearer, and also a type synonym for shopping lists, and an actual shopping list, too:
type Name = String type PriceInCents = Int type ShoppingListItem = (Name, PriceInCents) type ShoppingList = [ShoppingListItem] shoppingList :: ShoppingList shoppingList = [ ("Bananas", 300) , ("Chocolate", 250) , ("Milk", 300) , ("Apples", 450) ]
Name is now
ShoppingListItem is a tuple of
PriceInCents, which is the same as saying it’s a tuple of
ShoppingList is the same thing as
[(Name,PriceInCents)], which is a list of tuples, and is the same thing as
All of these type aliases makes it much easier to understand what the programmer who wrote this intended. Especially the type
PriceInCents. If we didn’t have this, we would have no idea what the numbers in each tuple are supposed to represent. We would have to either work it out by looking at all of the code, or hope that the programmer had written some helpful comments in the code.
Let’s look at the finished program that will tell us how much the total price of a shopping list is, in cents:
type Name = String type PriceInCents = Int type ShoppingListItem = (Name, PriceInCents) type ShoppingList = [ShoppingListItem] shoppingList :: ShoppingList shoppingList = [ ("Bananas", 300) , ("Chocolate", 250) , ("Milk", 300) , ("Apples", 450) ] sumShoppingList :: ShoppingList -> PriceInCents sumShoppingList  = 0 sumShoppingList (x:xs) = getPriceFromItem x + sumShoppingList xs getPriceFromItem :: ShoppingListItem -> PriceInCents getPriceFromItem (_, price) = price main :: IO () main = putStrLn ("Price of shopping list is " ++ show (sumShoppingList shoppingList) ++ " cents.")
We have two new functions to look at here.
The first is
getPriceFromItem. The name pretty much explains exactly what it does. It uses pattern matching on a
ShoppingListItem (which is a tuple), and extracts only the second element of the tuple.
There are actually two functions that work with tuples called
snd that pull out the first or second element of a tuple respectively. We could have just defined
getPriceFromItem as being
snd, because we’ve pretty much just re-created it here, but it’s useful to show you how to do it.
The second new function is
sumShoppingList. This is using recursion to go over each item in the list, and apply the
getPriceFromItem function to them, adding the prices together as it does so.
sumShoppingList is evaluated, one way to think about how it can do the work to find a value is to imagine what it would look like if all of the expansions of
sumShoppingList had already taken place inside the body of the function. This is, then, an equivalent expression to
getPriceFromItem ("Bananas", 300) + (getPriceFromItem ("Chocolate", 250) + (getPriceFromItem ("Milk", 300) + (getPriceFromItem ("Apples", 450) + 0)))
After this we can imagine what it’d be like after all the
getPriceFromItem functions have been applied to their tuple arguments, this is an equivalent expression:
300 + 250 + 300 + 450 + 0
It’s pretty easy to see how this is equal to 1300.
Going from the expanded recursion form to the single number is an example of what’s called folding, and it involves reducing a list to a single value.
We’ve seen this pattern a fair bit so far. Let’s look at it some more with a few more recursive functions:
joinStrings :: [String] -> String joinStrings  = "" joinStrings (x:xs) = x ++ joinStrings xs sumIntegers :: [Integer] -> Integer sumIntegers  = 0 sumIntegers (x:xs) = x + sumIntegers xs -- subtracts all subsequent numbers from -- the first number subtractNums :: Num a => [a] -> a subtractNums  = 0 subtractNums (x:xs) = x - subtractNums xs productOfIntegers :: [Integer] -> Integer productOfIntegers  = 1 productOfIntegers (x:xs) = x * productOfIntegers xs
If you look across all of those functions, and try to see what’s similar about them, you may notice some interesting things:
Firstly, there is a single value for the empty list case. This is called the base value. The case is called the base case, because it’s where the recursion ends.
Secondly, there is an operation being applied between each element of the list. For
(*). This is called the folding function, because it’s what Haskell uses to do the folding after the recursion has been fully expanded.
Thirdly, and a little more subtle, is that all of these functions fold to the right, which means the recursive function application happens at the right. This is why they’re called right folds. If we had our recursion on the left, it works differently.
If you remember, functions are values as well, which means we can pass a function into another function as a value. We can also return a function as a result. In fact, all functions of more than one argument do this. Let’s look at all the examples of the above, rewritten using the generalised fold right function, which takes a function as its first argument:
joinStrings :: [String] -> String joinStrings xs = foldr (++) "" xs sumIntegers :: [Integer] -> Integer sumIntegers xs = foldr (+) 0 xs subtractNums :: Num a => [a] -> a subtractNums xs = foldr (-) 0 xs productOfIntegers :: [Integer] -> Integer productOfIntegers xs = foldr (*) 1 xs
So, it seems
foldr takes three arguments! The first is a function of two arguments: the folding function. The second is the base value, and the third is the list we’re folding over.
This is what the type signature of
foldr looks like:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
length is generalised to work on any kind of
Foldable, so is
length are part of the
Let’s imagine what the type of
foldr would actually be specialised to for the
joinStrings function, given that it’s dealing only with lists as its
Foldable instance we’re dealing with is the one for List, so we could replace the “
Foldable t => t” part with List like this:
foldr :: (a -> b -> b) -> b ->  a -> b
but we can just write
 a as
foldr :: (a -> b -> b) -> b -> [a] -> b
Foldable => t constraint and type is now replaced with List, because
Foldable related to the container type, which is List, and that is now fully specified.
Next, what about the type of
a? Well, we know
foldr takes three arguments, and the third is a list of
String in the body of
joinStrings because it looks like this:
joinStrings xs = foldr (++) "" xs and
xs is of type
a must be
String. We take a List of Strings. While we’re at it, b will be String, too (because the
(++) function, which we’re using, has the same type on both of its arguments. So we can rewrite the type for
foldr as specialised inside
joinStrings like this:
foldr :: (String -> String -> String) -> String -> [String] -> String
That makes more sense in that case. We fold over our list of strings, joining them together with
(++) as we go, and our base case for when we have only got the empty list left is the empty string
Next, though, we’ll look at
sumShoppingList again, and how to make it use
foldr. We'd just like to remind you about the type of the folding function in
(a -> b -> b), and that means that first argument can be a different type than the second, but doesn’t have to, but that the second one must be the same type as the result.
sumShoppingList :: ShoppingList -> PriceInCents sumShoppingList  = 0 sumShoppingList (x:xs) = getPriceFromItem x + sumShoppingList xs sumShoppingList' :: ShoppingList -> PriceInCents sumShoppingList' xs = foldr getPriceAndAdd 0 xs getPriceAndAdd :: ShoppingListItem -> PriceInCents -> PriceInCents getPriceAndAdd item currentTotal = getPriceFromItem item + currentTotal getPriceFromItem :: ShoppingListItem -> PriceInCents getPriceFromItem (_, price) = price main :: IO () main = putStrLn ("Price of shopping list is " ++ show (sumShoppingList shoppingList) ++ " cents.")
sumShoppingList’ is our function that uses
foldr, which also uses another new function
getPriceAndAdd, whose type could be thought of as
a -> b -> b which matches the first argument of
0 is our base value just like in our recursive version.
Haskell already has “built-in” functions for
product and joining strings together (
concat generally concatenates lists of the same type together, so will work fine on
String values). Here, we’ve just been illustrating how they could be built to show you how basic recursion works. The built-in functions are more generalised to work on any
Your homework is to go through all the functions we saw, think about how they work, using pen & paper to work out the steps involved in evaluating them applied to some values of your own choosing.
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.