Happy Learn Haskell Tutorial Vol 1

Buy now at Leanpub

Please Buy now at Leanpub

Written and illustrated by GetContented.

Published on 2016-08-14.


Contents

Main Table of Contents
Previous chapter: 10. A Dream Within a Dream
11. More Shopping
... 11.1. Tuples
... 11.2. Type Aliases (or Type Synonyms)
... 11.3. The Final Program
... 11.4. More Recursion Explained
... 11.5. Folding
... 11.6. Using foldr
... 11.7. Built in Recursive Functions
... 11.8. Homework
Next chapter: 12. How To Write Programs

11. More Shopping 🔗

Let’s take a look at a program which will let us work out how much our shopping list will cost in total.

11.1. Tuples 🔗

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.

11.2. Type Aliases (or Type Synonyms) 🔗

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)
               ]

So Name is now String, PriceInCents is Int, ShoppingListItem is a tuple of Name and PriceInCents, which is the same as saying it’s a tuple of String and Int, and ShoppingList is the same thing as [(Name,PriceInCents)], which is a list of tuples, and is the same thing as [(String,Int)].

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.

11.3. The Final Program 🔗

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 fst and 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.

11.4. More Recursion Explained 🔗

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.

When 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 sumShoppingList shoppingList:


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.

11.5. Folding 🔗

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 joinStrings, it’s (++). For productOfIntegers, it’s (*). 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.

11.6. Using foldr 🔗

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

Just like length is generalised to work on any kind of Foldable, so is foldr. Actually, foldr and length are part of the Foldable typeclass.

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

First, the 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 [a], so:


foldr :: (a -> b -> b) -> b -> [a] -> b

Okay, the 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 [String].

So, 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 foldr. It’s (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.")

So, 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 foldr, and 0 is our base value just like in our recursive version.

11.7. Built in Recursive Functions 🔗

Haskell already has “built-in” functions for sum, 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 Foldable instance.

11.8. Homework 🔗

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.


Main Table of Contents
Previous chapter: 10. A Dream Within a Dream
11. More Shopping
... 11.1. Tuples
... 11.2. Type Aliases (or Type Synonyms)
... 11.3. The Final Program
... 11.4. More Recursion Explained
... 11.5. Folding
... 11.6. Using foldr
... 11.7. Built in Recursive Functions
... 11.8. Homework
Next chapter: 12. How To Write Programs