Please Buy now at Leanpub

Written and illustrated by GetContented.

Published on 2016-08-14.

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

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

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.

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.

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.

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.

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.

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.

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