# Introduction to Haskell

Haskell is a purely functional computer programming language. To be more precise, it is a *polymorphically-*, *statically-* and *strongly-typed*, *lazy*, *compiled*, and *pure* functional programming language. We will explore what all of those terms mean soon enough, but let’s start by reviewing what functions are, what functional programming is and how functional programming differs from imperative programming.


# Functions

In Haskell, functions work exactly as they do in mathematics. In mathematics, functions define the unambiguous dependence of the output value to its arguments, i.e., they map the input values to the output. This means that for any combination of arguments, there can only be one result. Let’s look at a simple example of a function that takes one argument and multiplies it by three:

$$
f (x) = 3 \* x
$$

 For any input value x, there is only one possible output:

$$
f (2) = 6
$$

$$
f ( -5) = -15
$$

This is exactly what we mean when we say Haskell is a purely functional programming language – because it focuses on pure functions whose output values are entirely determined by their arguments. This means that there are no side-effects to functions in Haskell, a function with the same arguments will always produce the same result no matter what else is going on in the program it is in, which makes them very reliable.

In other words, Haskell functions do not allow anything besides simply taking inputs from their arguments and producing a return value, so things like printing on screen, reading from and writing to files are off the table for Haskell functions. However, that would mean Haskell cannot be very useful, and that is why it is still possible to integrate these important and useful features through the use of Monads (we will not touch Monads for some time, but for now just trust me that Haskell can have very real applications – after all, Cardano is built with Haskell).

In Haskell, we can define a function by using an equation that specifies:

1. The function name
2. The names of its arguments
3. The function body that specifies how the result will be calculated

To define our tripling function above in Haskell, we would write:

```haskell
triple x = 3 * x
```

where `triple` is the function name, `x` is its only argument and`3 * x`is the function body. Notice that in Haskell, there is no need for parentheses that wrap around the arguments. The function name and the first argument, as well as any subsequent arguments, are simply separated by a space.

When the function is applied to actual arguments, the body of the function receives the arguments and the result is calculated (with curly parentheses signifying comments in the block below):

```haskell
triple 4
= { applying triple }
3 * 4
= { applying * } 
12
```


# Functional Programming vs Imperative Programming

Now that we have taken a look at functions in Haskell, let’s explore the concept of functional programming. In functional programming, the basic method of computation is the application of functions to arguments. Therefore, functional programming is best described as a programming style, and functional programming languages support and encourage this style.

On the other hand, in imperative programming the basic method of computation is changing stored values, i.e. functions in imperative programming languages are not purely mathematical functions, but rather a sequence of instructions that the program should follow to get to the result. To better understand this, let’s see how a task of calculating the sum of natural numbers between `1` and `n` would normally be handled by an imperative language, C:

```c
int sum = 0;
for (i = 1; i <= n; i++) {
    sum = sum + i;
}
```

The above program first initialises a variable `sum` to zero, and then loops (repeats the same action) through all the numbers from `1` to `n`, updating the stored value of  the `sum` variable on each iteration. In the case of `n = 3`:

```c
sum = 0;
{ first iteration }
i = 1;
sum = 1;
{ second iteration }
i = 2;
sum = 3;
{ third iteration }
i = 3;
sum = 6;
```

Now let's take a look at how that task could be handled by Haskell – we can achieve this with a combination of two functions:

1. `[n .. m]` – which produces a list of numbers from `n` to `m`, e.g. `[1..3] => [1, 2, 3]`
2. `sum`  – which produces the sum of a list

{% hint style="info" %}
`sum` is a predefined function in the Haskell standard library called Prelude, which is imported by default into all Haskell modules. Libraries are collections of functions already written by people to solve various problems, and we can use them without having to rewrite existing solutions ourselves.
{% endhint %}

```haskell
sum [1..3]
= { applying [..] }
sum [1, 2, 3]
= { applying sum }
1 + 2 + 3
= { applying + }
6
```

The above example shows that executing Haskell programs triggers a sequence of function applications – the basic method of computation in functional programming. In functional programming, the code tells the program what to calculate, but not explicitly how to get to the end result following a sequence of steps.

That brings us to another important thing – Haskell has no variable assignments. The equality sign `=`  in Haskell is not the assignment operator as in imperative languages, but instead the equivalent of the mathematical equal sign.


# Installing Haskell

Alright, time to finally install Haskell and start writing some code. The recommended way to install Haskell is via GHCup ([https://www.haskell.org/ghcup/](https://www.haskell.org/ghcup/#)), which will get you up and running quickly with several tools, most notably, the Glasgow Haskell Compiler (GHC).

We mentioned at the start that Haskell is a compiled language, which means we have to compile our programs to computer code first before being able to run them. However, GHC comes with an interpreter (GHCi) which allows us to play with Haskell interactively without having to compile our code beforehand.


# Haskell Modules

Haskell code is organised into modules, which are files that contain the Haskell source code. Each module corresponds to one single file, and the standard extension for Haskell modules is `.hs`. Each module should start with the name of the module which is also the same name of the corresponding file, e.g. module `Triple.hs`:

```haskell
module Triple -- module name
(
    triple -- module interface (what is explicitly exported)
) where

{- Module contents -}
triple x = 3 * x -- function declaration
```

First, we have the module name `Triple`, followed by the module interface wrapped in parentheses. The module interface states what gets exported from this module, i.e. if this module is imported somewhere else, the`triple`function is the only thing that would be usable from this module. If we had another function declared in the module contents (e.g. `quadruple`), that function would not be exported unless specified in the existing module interface. However, the module interface is optional, and if omitted, all the declarations from the module will be exported.

Comments serve the purpose of documenting our code and anything we put in comments will not be evaluated in the program. Haskell comments can be single-line and multi-line – single-line comments start with `--`, and multi-line comments are wrapped between `{- -}`. Any comments in this guide will also follow the same format.


# Loading Modules into GHCi

Before we move on, let's see how we can load modules we create into GHCi, so that we can use any functions we define. We create a new file, e.g. `Practice.hs`, and define our module in there (remember, the module name should match the file name), and define our `triple` function from before:

```haskell
module Practice where

triple x = 3 * x
```

We can now launch GHCi from the terminal and load our module using its relative file path using `:load`, making the function available for use:

```haskell
$ ghci
GHCi, version 8.10.2: https://www.haskell.org/ghc/ :? for help

{- Assuming our Practice.hs file is in the same directory from 
 which we launched GHCi -}
 
ghci> :load Practice.hs
[1 of 1] Compiling Practice ( Practice.hs, interpreted )
Ok, one module loaded.

*Practice> triple 3
9
```


# Expressions

We said applying functions to arguments is the basic method of computation in Haskell – the building blocks of Haskell programs. In that sense, expressions in Haskell would be what those building blocks are made of. Expressions can represent some primitive values, e.g. numbers, characters, or booleans (`True`/ `False`), and in that case, they are **irreducible** expressions, meaning they cannot be further simplified. On the other hand, there are **reducible** expressions, which can be evaluated to their final irreducible form.

Let's use GHCi to explore some Haskell expressions (`ghci>` denotes code that is evaluated in GHCi):

```haskell
ghci> 2 + 2 -- reducible expression
4
ghci> 10 -- irreducible expression
10
```

Notice that any reducible expression is actually a function applied to some arguments (in this case the addition operator `(+)`. So any function in Haskell is at its core – an expression.


# Laziness

We are starting to define our own functions now, so it is a good time to explain the concept of laziness in Haskell. Haskell is a **lazy** programming language, which means it does not evaluate expressions until really necessary. The opposite of lazy evaluation is strict evaluation, in which all expressions in a function call are evaluated before they are passed to the function.

Let's take a look at an example to better understand this:

```haskell
ghci> f1 x y = x + 1
```

We see the function `f1` takes in two arguments, but completely ignores its second argument \`y\` during evaluation. Let's see what happens when we actually pass some arguments to the function:

```
ghci> f1 1 (2^58)
2
```

Of course, the final result is `2`, because `1 + 1 = 2`, but what happened with our second argument `(2 ^ 58)`? It was never needed during function execution so it was actually never evaluated. From this example, we can see how lazy evaluation can save computational time by not doing unnecessary computations.

However, there is also a drawback to this strategy - our second parameter was not completely ignored, but instead stored in memory as an unevaluated expression (2 ^ 58). These unevaluated expressions can build up in heap memory and cause memory leakage. That is, our programs can have increased memory usage for no useful reason and if they consume all our system memory, the program will crash.


# Immutability

At this point in our training, you need to learn that all values in Haskell are immutable! What exactly does that mean? It means that when you apply a function to some argument, the value of that argument cannot be changed. Instead, you create a new value each time. That means "variable assignment" does not exist in Haskell. Instead, we only assign a *name* to an expression and we know that that *name* will always evaluate only that expression.

```haskell
ghci> let a = [1,2,3]
ghci> reverse a -- reverse is a function that reverses a list...
[3,2,1]
ghci> a -- ...but the value of the expression "a" never changes
[1,2,3]
```


# Introduction

As we mentioned at the start, Haskell is a **strongly-typed** language so let's expand on that. Haskell is very serious about types and strongly-typed means that each **expression** in Haskell has an associated **type** to its value. Expression types can be basic, which are built-in the language – the likes of **Int**, **Integer**, **Float**, **Double**, **Char**, **String** and **Bool**. Notice that type names always start with an uppercase letter. Types can also be **polymorphic** (which is why Haskell is also a **polymorphically-typed** language), in which case they are specified through **type variables** beginning with a lowercase letter, but more on that shortly.


# Basic Types

## Bool – logical values&#x20;

**Bool** is a logical data type that can be either `True` or `False`.

## Int – fixed-precision integers

**Int** can contain integers, both negative and positive whole numbers (e.g. `-50`, `50`) up to a certain size which is limited by a fixed amount of memory, hence the term fixed-precision. GHC can hold values in the range of `(-2^63)` to `(2^63 - 1)` for **Int** types - going outside those ranges will yield unexpected results.

## Integer – arbitrary-precision integers&#x20;

**Integer** is the same as Int except it does not have a limit to the values it can hold. Performance-wise, it is better to use Int if we know our values will not go out of range, as most computers have built-in hardware for dealing with fixed-precision integers.

## Float – single-precision floating-point numbers

**Float** can contain decimal numbers (e.g. `-1.5`, `6.23`, `50.0`) up to a certain precision which is limited by a fixed amount of memory. The term floating-point comes from this memory limitation, which limits the number of digits (precision) that can come after the decimal point based on the size of the number.

## Double – double-precision floating-point numbers

**Double** is the same type as float, containing decimal numbers but with double the memory assigned for storage for increased precision.&#x20;

## Char – single character

**Char** is a type for characters – it can hold any Unicode character including control characters such as `'\n'` (a new line character) or `'\t'` (tab stop character). **Char** type values must be enclosed in single quotes `''`.&#x20;

## String – strings of characters

**Strings** simply hold a string of characters – they are in fact a type `[Char]` (a list of **Char** type values) in Haskell. Strings must be enclosed in double-quotes `""`, e.g. `"Haskell is great"`.


# Static Type Check

We also said that Haskell is a **statically-typed** language, which means that each expression type is known at compilation time instead of run-time. This makes Haskell very reliable – if we successfully compile our program, we can be sure that no type errors will occur. This benefit does come at a cost of increased compilation time, and doing any changes to our program requires us to re-compile it.

Another feature of Haskell is type inference, which means that Haskell can automatically interpret types of expressions. This can make our code more concise, but it is still encouraged to explicitly specify the types when we define functions, i.e. to write functions by also including their **type signatures**. For our previous function `triple`, we could add a type signature to it in our `Practice.hs`:

```haskell
triple :: Int -> Int -- function type signature
triple x = 3 * x -- function definition
```

`triple :: Int -> Int` reads as "`triple` is a function that takes in one argument of the type `Int` and produces a result of a type `Int`". Now that we have altered our module code, we need to reload the practice module in order to apply the changes in GHCi:

```haskell
*Practice> :r Practice -- :r stands for :reload
Ok, one module loaded.

*Practice> :t triple -- :t stands for :type
triple :: Int -> Int

*Practice> triple 3
9
```

But what happens if we try to apply our `triple` function to a floating-point number?

```haskell
*Practice> triple 3.5
<interactive>:5:8: error:
 • No instance for (Fractional Int) arising from the literal ‘3.5’
 • In the first argument of ‘triple’, namely ‘3.5’
 In the expression: triple 3.5
 In an equation for ‘it’: it = triple 3.5
```

We get a **type error** because we strictly defined the function as one that takes in an `Int` as its only argument, but we passed in a floating-point number.&#x20;

#### Polymorphism

So how can we make our function accept both `Int`and `Float`? To do that, we can use Haskell's polymorphism and specify a polymorphic type of `Num a` (an **overloaded type** specified with a **type class** - more on those on the next page), which supports both integer and floating-point numbers:

```haskell
triple :: Num a => a -> a
triple x = 3 * x
*Practice> :r
*Practice> triple 3.5
10.5
```

The line `triple :: Num a => a -> a` now reads as "`triple` is a function that takes in one argument of type `a` and gives a result of type `a` where the type of `a` is `Num`". So here we see an example of **polymorphism** where we can work with different types for the same function argument. Note that we use the variable named `a` as a placeholder for the **type** **class** `Num`, but it could be any valid name starting with a lowercase character.


# Polymorphic and Overloaded Types

We have already touched upon **polymorphic types** in our `triple` function when we made it work with both integers and floating-point numbers. We used `Num a` in the **function's type signature** to specify that it can accept both number types as arguments. The `Num` is a class constraint and `a` is the **type variable** in our function signature. `triple :: Num a => a -> a` reads as "for any type `a` that is an instance of the **class `Num`**, the function `triple` has the type signature `a -> a`".

Any type that has a **class constraint** is called an **overloaded type**, and hence our `triple` function is an **overloaded function**. We can even also specify a **type variable** without the class constraint, in which case that type is **completely polymorphic** and any type can fill the arguments' place. For example, this is used in several list functions we used earlier, as their results do not depend on the types of elements that fill the lists. For example, the `head` (which returns the first element of a list) and `tail` (which returns the list excluding the first element) functions must work regardless of what type the elements in the list are. Therefore, their type signatures are:

```haskell
head :: [a] -> a
-- a list of type a's returns a type a, whatever type a is for that list

tail :: [a] -> [a]
-- a list of type a's returns a type [a], whatever type a is for that list
```


# Data Structure Types

We have explored the basic types of Haskell. Now let's take a look at the data type structures - **lists** and **tuples**, starting with **Lists**.


# Lists

**Lists** are sequences of elements of the **same type** and are a key component of Haskell. This means that a list can only hold elements of the same type, e.g. a list of `Ints` as we used in our example function - `sum`. To create lists in Haskell, we put their elements in square brackets and separate them with commas:

```haskell
[False, False, True] :: [Bool] -- a list of booleans
[1, 3, 5] :: [Int] -- a list of integers
['a', 'b', 'c'] :: [Char] -- a list of characters
```

Lists can also contain other lists:

```haskell
[[1, 2, 3], [4, 5, 6]] :: [[Int]] -- a list of lists of integers
```

But remember - lists are sequences of elements of the same type, so a list of lists must not contain lists of different types. For example, we cannot combine a list of `Ints` and a list of `Chars` into a single list of lists:

```haskell
ghci> x = [[1, 2, 3], ['a', 'b', 'c']]

<interactive>:2:7: error:
    • No instance for (Num Char) arising from the literal ‘1’
    • In the expression: 1
      In the expression: [1, 2, 3]
      In the expression: [[1, 2, 3], ['a', 'b', 'c']]
```

Lists can also be empty (`[]`) and a special case called a **singleton** list is (`[[]]`), which is a list with its single element being an empty list. Lists in Haskell can also be infinite.


# List Functions

Haskell comes with a number of useful functions for working with Lists in its `Data.List` module. This module is loaded by default in GHCi's Prelude:

```haskell
ghci> head [1, 2, 3] -- get the first element of a list
1

ghci> tail [1, 2, 3] -- exclude the first element from a list
[2, 3]

ghci> [1, 2] ++ [3, 4] -- join two lists together
[1, 2, 3, 4]

ghci> [1 .. 5] -- create a list of integers from 1 to 5
[1, 2, 3, 4, 5]

ghci> [1, 3 .. 10] -- list enumeration of integers with a step
[1, 3, 5, 7, 9]

ghci> [5, 4 .. 1] -- list enumeration of integers backwards
[5, 4, 3, 2, 1]

ghci> ['a' .. 'z'] -- enumeration even works with Chars
"abcdefghijklmnopqrstuvwxyz"

ghci> replicate 3 True -- create a list by replication
[True, True, True]

ghci> take 2 [1 .. 5] -- take the first 2 elements of a list
[1, 2]

ghci> drop 2 [1 .. 5] -- drop the first 2 elements of a list
[3, 4, 5]
```

As we mentioned before, everything in Haskell is immutable which means we cannot change an existing list, but we can create new ones from it. Lists are constructed from an empty list `[]` using an operator called cons `(:)` that constructs a list by adding new elements to the start of the list. For example, the list `[1, 2, 3, 4, 5]` is constructed in the following way:

```haskell
[1, 2, 3, 4, 5] => 1 : (2 : (3 : (4 : (5 : []))))

5 : []
4 : [5]
3 : [4, 5]
2 : [3, 4, 5]
1 : [2, 3, 4, 5]
[1, 2, 3, 4, 5]
```


# Tuples

**Tuples**, unlike lists, can contain elements of **different types**. The elements of a tuple are enclosed in round parentheses and separated by commas:

```haskell
("Cardano", True) :: (String, Bool)
```

The above is an example of a **tuple pair** that is comprised of two elements, in this case, a string and a boolean. Notice that the tuple type is dependent on its elements – both the number of elements and their individual types. Unlike with lists, where we have one clear type for any single list regardless of its length, tuples must be finite and the type of each element must be known in order for the Haskell type system to able to work properly. The length of a tuple is sometimes referred to as its **arity**.

```haskell
[1] :: [Int] -- The type of the list is the same...
[1, 2, 3] :: [Int] -- ...regardless of its length.

(1, 2) :: (Int, Int) -- The type of the tuple changes...
(1, 2, False) :: (Int, Int, Bool) -- ...with its length (and element types).
```

**Tuples** are most commonly used as key-value pairs – a data structure for storing and retrieving data. That is why I said **pairs** are the most common of tuples – for example, a name–address pair or a dictionary word-definition pair.


# Function Types

We know that **functions** in Haskell are **expressions** and each expression must have a type, so what types can a function have? Functions take in some arguments and create a result of some type which can be the same as some (or all) of its arguments or a different one. We have already touched upon the subject of function types in our example function `triple`:

```haskell
triple :: Int -> Int
triple x = 3 * x
```

In this case, the type of our function triple is `Int -> Int` – it takes an`Int`as its only argument and returns an`Int`as the result. As functions are expressions, we can use them as any other type of data, for example, we can create a list of functions:

```haskell
ghci> funList = [(+), (*)]
-- (+) and (*) are functions for addition and multiplication
ghci> :t funList
Num a => [a -> a -> a]
```

We can see that `funList` is a list of a certain type – specifically, a **function type** that takes two arguments of type `Num` and returns a `Num` type as its result.


# Curried Functions

Functions in Haskell are also free to **return functions** as their results. This brings us to **curried functions** which take in **one argument at a time** and **return a function** that takes in additional arguments. Actually, all functions in Haskell with multiple arguments are applied this way (unless explicitly stated otherwise) – the function is first applied to the first argument and returns another function that is then applied to the second argument and so on. Let's explore this with an example \`multiply\` function that takes in three numbers and multiplies them:

```haskell
ghci> multiply x y z = x * y * z
ghci> :t multiply
multiply :: Num a => a -> a -> a -> a

-- a -> a -> a -> a actually means:
Num a => a -> (a -> (a -> a))
```

That is, `multiply` takes the argument `x` of type `a` and returns another function that takes in the argument `y` (also of type `a`) and returns another function that takes in the argument `z` (also of type `a`) that then returns the final result (also of type `a`). To avoid unnecessary parentheses, the function arrow `->` associates to the right by convention, while the function application associates to the left:

```haskell
multiply x y z
-- is actually:
((multiply x) y) z
```


# Partial Application

**Curried functions** enable **partial application**, which can be used to call a function with only some of its arguments and **get a function back as a result** for further use. That way, we can create new functions from existing ones which can serve as a powerful tool. For example, with our `multiply` function, we can create a function that always multiplies a number by`2`:

```haskell
ghci> multiplyBy2 = multiply 1 2

ghci> :t multiplyBy2
multiply2 :: Num a => a -> a -- this function takes only 1 argument

ghci> multiplyBy2 5
10
```


# The Layout Rule

Before we dive into working with functions in Haskell, let's explore the **layout rule**. The layout rule states that each definition at the same level must begin at the same line position (column) in the script. This allows us to determine the groupings of different definitions simply from **indentation**. Let's define a function that adds the squares of two numbers together:

```haskell
sumSquares x y = a + b
  where
    a = x ^ 2 -- (^) is the power function
    b = y ^ 2
    
ghci> sumSquares 2 5
29
```

From the indentation, it is obvious to Haskell that `a` and `b` are **local definitions** in the function `sumSquares`, defined using the `where` keyword. **Local definitions** exist as intermediate helper expressions for structuring our functions and making our code more readable. It is also possible to wrap the local variables `a` and `b` in curly braces to explicitly state the grouping in which case the layout does not matter (although it's considered best practice to use the layout rule to give our code better readability), but we need to also explicitly separate each local definition with `;`:

```haskell
sumSquares x y = a + b
  where
    {
      a = x ^ 2; -- we need to separate expressions with ';' in this case
      b = y ^ 2
    }

ghci> sumSquares 2 5
29
```


# Local Definitions

We already saw how we can use `where` to define local helper expressions, but there is also another way. The `let`-`in` construct also allows us to define local expressions with the syntax `let <declarations> in <expression>`:

```haskell
sumSquares2 x y =
  let
    a = x ^ 2
    b = y ^ 2
  in
    a + b

ghci> sumSquares2 2 5
29
```

We can also use `let` -`in` and `where` in combination – for example, let's write a function that checks whether the sum of the squares of two numbers is a multiple of five:

```haskell
sumSquaresM5 x y =
  let
    sum = a + b
  in
    mod sum 5 == 0 -- (mod) is the modulo operator 
  where
    a = x ^ 2
    b = y ^ 2
```

We know a number is a multiple of five if the remainder of its division by five is zero. A thing to note is that there is a difference between `let`-`in` and `where`. What we define in `where` declarations is accessible to any code above it. However, the declarations from the `let` block are only accessible in the `in` block of the same `let-in` clause. For example, we could try to calculate the remainder from the division by five in the `where` clause using the `sum`from the `let` clause, but it will not work:

```haskell
sumSquaresM5 x y =
  let
    sum = a + b
  in
    res == 0
  where
    a = x ^ 2
    b = y ^ 2
    res = mod sum 5 -- the "sum" expression from let-in is not accessible here
```

The compilation of the above would result in an error as `sum` is only accessible in the `in` clause of the code. This means that with `let`-`in` we can create **super-localised expressions** that aren't accessible anywhere outside the `in` code block.


# The Infix Operator

This is a good time to introduce the **infix operator** that helps us make code a bit more readable. Normally, we apply a function by writing `<FUNCTION> <ARGUMENT1> <ARGUMENT2>`, but we could also write it using the infix operator as ``<ARGUMENT1> `<FUNCTION>` <ARGUMENT2>``. This way, we make the code more readable – for example, in the case of`res = mod sum 2`, we can instead write:

```haskell
res = sum `mod` 2 -- using the infix operator ``
```

Which then reads as "`res` is equal to `sum modulo 2`". Note that the infix operator can be used this way for **functions that take in two arguments**. For functions with more than two arguments, we would need to add parentheses to explicitly create expressions (which return another function – [currying](/types-in-haskell/function-types/curried-functions)):

```haskell
ghci> multiply x y z = x * y * z

ghci> (1 `multiply` 2) 3
6
```


# Conditionals

**Conditionals** are a key construct in any programming language. They let us make decisions within our code based on certain values. In Haskell, we have a few different ways of writing conditional expressions, including **if-then-else statements**, **guarded equations** and **case expressions**.


# If-then-else Statements

The syntax in Haskell for if-then-else statements is:

```haskell
if <CONDITION> then <EXPRESSION1> else <EXPRESSION2>
```

where the `CONDITION` must be a **boolean expression**. If the condition evaluates to `True`, then `EXPRESSION1` is used, otherwise, `EXPRESSION2` is used. One other thing to note here is that **both expressions in the if statement must be of the same type**. For example, the statement:

```haskell
if True then 1 else "untrue"
```

is invalid because the type of `1` is `Int`, but the type of "`untrue"` is `String` (synonym for `[Char]` - a string is simply a list of characters).

Let's take a look at a simple example function using a conditional statement to decide on the final score on a race track given two arguments – the time achieved and the average time for the track in seconds:

```haskell
trackScore :: Float -> Float -> String
trackScore time avgTime =
  if time < avgTime
  then "Great! Your time is " ++ show (avgTime - time) ++ " seconds 
    below average!"
  else "Your time is " ++ show (time - avgTime) ++ " seconds above 
    average."
```

You have probably noticed this new function `show` – it is a method (function) from the `class Show` and it is used to represent the value of a type as a string. Hence, it has the following type signature:

```haskell
show :: a -> String
```

{% hint style="info" %}
We will explore classes in more detail later on - for now, just know that a `class` comes with certain **methods** (functions) it supports.
{% endhint %}

All the basic types (`Bool`, `String`, `Char`, `Int`, `Integer`, `Float` and `Double`) are instances of the `Show` class which enables us to use the `show` function and get their representation as a string:

```haskell
ghci> show 252.5
"252.2"
```

In our function `trackScore`, we consider the two cases where the given time is lower than the average time and when it is higher than the average time. But what if it is exactly the same?

```haskell
ghci> trackScore 10 10
"Your time is 0.0 seconds above average."
```

The output is not wrong, but ideally, we would like to see a third version of the output for this particular case. We could nest another if statement in our existing code and write:

```haskell
trackScore :: Float -> Float -> String
trackScore time avgTime =
  if time < avgTime
    then "Great! Your time is " ++ show (avgTime - time) ++ " seconds 
      below average!"
    else 
      if time == avgTime
        then "Your time is on par with the average time!"
        else "Your time is " ++ show (time - avgTime) ++ " seconds above 
          average."
      
ghci> trackScore 10 10
"Your time is on par with the average time!"
```

The output is fine now, but with every **nested if statement**, the code gets harder to read. Turns out there is a way to make it look nicer – with **MultiWayIf**.


# MultiWayIf

**MultiWayIf** allows us to create multiple cases for our if statements **without nesting** them. We define a sequence of expressions that evaluate to either `True` or `False` (conditions called **guards**) and associate an expression with each of them:

```haskell
if | <CONDITION1> -> <EXPRESSION1>
   | <CONDITION2> -> <EXPRESSION2>
   | ...
   | <CONDITIONx> -> <EXPRESSIONx>
   | otherwise    -> <EXPRESSION>
```

The symbol `|` can be read as "such that..." or "where...". The guards are evaluated from top to bottom, and the expression associated with the first guard that is `True` is chosen for further evaluation. The `otherwise` function simply always evaluates to `True` and the expression associated with it will always be further evaluated if none of the guards before it evaluates to `True`. It gives us a convenient way to make sure that we have handled all possible cases. It is not necessary to add the `otherwise` guard at the end, but **if all the possible cases are not met, we will end up with an error at runtime**.

One more thing we have to do in order to use the `MultiWayIf` is to **enable the extension** in GHC. GHC has a number of special features that are disabled by default (like the `MultiWayIf`) so we have to add a line above our module declaration in the following format to enable it:

```haskell
{-# LANGUAGE MultiWayIf #-} 
module Practice where
...
```

Let's switch our `trackScore` function to use `MultiWayIf` instead, but not include the case where `time == avg`. It will result in an error at **runtime** (not during compilation) because the case we entered has not been defined:

```haskell
trackScore :: Float -> Float -> String
trackScore time avgTime = 
  if | time < avgTime -> "Great! Your time is " ++ show (avgTime - time) 
         ++ " seconds below average!"
     | time > avgTime -> "Your time is " ++ show (time - avgTime)
         ++ " seconds above average."

ghci> :r
[1 of 1] Compiling Practice ( practice.hs, interpreted )

*Practice> trackScore 10 10
"*** Exception: practice.hs:(74,1)-(76,89): Non-exhaustive patterns in 
function trackScore"
```

Let's fix it up:

```haskell
trackScore :: Float -> Float -> String
trackScore time avgTime = 
  if | time < avgTime -> "Great! Your time is " ++ show (avgTime - time) 
         ++ " seconds below average!"
     | time > avgTime -> "Your time is " ++ show (time - avgTime) ++ " 
         seconds above average."
     | otherwise -> "Your time is on par with the average time!"
```

This already reads much better than our first implementation with nested `if-statements`, but there is a way to make it even nicer by using **guarded equations**.


# Guarded Equations

**Guarded equations** provide an alternative to if-else statements and are especially useful when we need multiple ifs in our code. Like [`MultiWayIfs`](/defining-functions-working-with-functions/conditionals/multiwayif), they represent a sequence of expressions that evaluate to either `True` or `False` (conditions) which are individually called guards and are used to decide the flow of the program. The syntax is very similar to the `MultiWayIf` syntax and allows us to get rid of the `if` keyword altogether:

```haskell
trackScore :: Float -> Float -> String
trackScore time avgTime  -- equation sign moved to each expression below
  | time < avgTime = "Great! Your time is " ++ show (avgTime - time) ++ "
      seconds below average!"
  | time > avgTime = "Your time is " ++ show (time - avgTime) ++ " 
      seconds above average."
  | otherwise = "Your time is on par with the average time!"
```

Note that in the above implementation of **guarded equations**, we have **moved the equation sign** in the line `trackScore time avgTime`, and we have **replaced the ifs arrow** `(->)` with it.


# Case-of Statements

There is another type of conditional statement in Haskell - `case`-`of`. It uses pattern matching to determine the expression to be evaluated. If you are familiar with switch statements from imperative programming, this is their equivalent in Haskell. The syntax is:

```haskell
case <EXPRESSION> of
  <PATTERN1> -> <EXPRESSION1>
  <PATTERN2> -> <EXPRESSION2>
  ...
  <PATTERNx> -> <EXPRESSIONx>
  _          -> <DEFAULT_EXPRESSION>
```

The `_` is a **wildcard character**. It is a useful tool for when we do not really care about what the value of the expression might be. In this case, whatever that value is – we know what we want to do if none of our previous patterns matches and assign it the default expression. For example, we could define a function that returns the colour of a playing card based on its suit:

```haskell
cardColour :: String -> String
cardColour suit =
  case suit of
    "hearts" -> "red"
    "diamonds" -> "red"
    "spades" -> "black"
    "clubs" -> "black"
    _ -> "I am not familiar with this card suit."
    
ghci> cardColour "diamonds"
"red"
ghci> cardColour "ace"
"I am not familiar with this card suit."
```

That is, for the four valid suits we return their respective colours. Anything else is covered by the wildcard case and no matter what the value is, we always choose the same course of action.


# Pattern Matching

**Pattern matching** is similar to conditional statements and allows us to choose different paths for our functions based on the patterns of their arguments. These **patterns can be direct values or more general patterns of arguments** that the function takes in. Much like in [guarded equations](/defining-functions-working-with-functions/conditionals/guarded-equations), the patterns are evaluated from top to bottom and the first one that matches the input arguments is selected for further evaluation. We can define our previous function `cardColour` using pattern matching with **direct values**:

```haskell
cardColour :: String -> String
cardColour "hearts" = "red"
cardColour "diamonds" = "red"
cardColour "spades" = "black"
cardColour "clubs" = "black"
cardColour _ = "I am not familiar with this card suit."

ghci> cardColour "diamonds"
"red"
ghci> cardColour "ace"
"I am not familiar with this card suit."
```

That is, we define multiple patterns for our function to account for different card suits and the wildcard character performs the same function as in the [`case`-`of`](/defining-functions-working-with-functions/conditionals/case-of-statements) example. Pattern matching gets more powerful when we use it with lists and tuples to build larger patterns.


# Tuple Patterns

We can think of a tuple pattern as a tuple of lower-level patterns – the lower-level patterns match individual elements in the tuple. That tuple of patterns itself makes a full pattern that matches any tuple **with the same length and whose elements match the internal patterns**. We could use tuple patterns for functions that return the suit and the rank of a playing card represented by a tuple:

```haskell
getSuit :: (String, String) -> String
getSuit (suit, _) = suit

getRank :: (String, String) -> String
getRank (_, rank) = rank

ghci> getSuit ("Hearts", "Ace")
"Hearts"
ghci> getRank ("Hearts", "Ace")
"Ace"
```

We check that the tuple passed in is of arity two, and then return the first or second element depending on what we want to get.


# List Patterns

As with tuple patterns, we can think of list patterns as a combination of two types of patterns as well. The first type is the patterns for each individual element we define which forms a list of patterns. The second type comes from the fact that that same list of patterns is a pattern itself. For example, let's say we want to define a function that takes in a list of any type and checks whether it contains exactly 4 elements:

```haskell
check4 :: [a] -> Bool
check4 [_, _, _, _] = True
check4 _ = False
```

That is, we first check the pattern of `[_, _, _, _]`, which is a list of four patterns itself, one for each individual element in the expected list, and for each of those we use the wildcard because we do not care about what the value of the element is. We only care that the element exists there and that there are exactly four elements in the list. If that first pattern doesn't match, we simply use the wildcard to say that whatever is there, we already know it does not contain exactly 4 elements and return `False`.

But there is also another list pattern that is very useful and it takes advantage of the cons `(:)` constructor used for constructing lists. We know [from before](/types-in-haskell/data-structure-types/lists/list-functions) that a list represented as `[1, 2, 3]` is actually constructed as `1 : 2 : 3 : []` using the `(:)` constructor, so we can use that form in our list patterns (but we must parenthesise patterns using cons):

```haskell
check4 :: [a] -> Bool
check4 (_ : _ : _ : _ : []) = True
check4 _ = False

ghci> check4 [1,2,3]
False
ghci> check4 [1,2,3,4]
True
```

In fact, we can represent any list **with at least one element** with the following pattern:

```haskell
(x : xs)
```

In this pattern, `x` is **the first element** of the list and `xs` is **the tail of the list** (whatever remains after excluding the first element). The `xs` can be a list of `n` number of elements or it could even be just an empty list `[]`, in which case, the whole expression `(x : xs)` would be a list of just one element. Note that `x` and `xs` are simply standard names in this pattern, but we could use other names if we'd like to.

This means we can **pattern match on lists with an undefined number of elements**, unlike with tuples, where we have to match a finite number of elements. For example, the list functions `head` and `tail` use exactly this pattern to select the first element and the tail of a list, respectively:

```haskell
head :: [a] -> a
head (x : _) = x

tail :: [a] -> [a]
tail (_ : xs) = xs
```

We said that the pattern `(x : xs)` holds true for any list with at least one element, so what happens if we call these functions on an empty list?

```haskell
ghci> head []
*** Exception: Prelude.head: empty list

ghci> tail []
*** Exception: Prelude.tail: empty list
```

That case is covered by throwing an error since empty lists have neither a head nor a tail.


# Lambda functions

**Lambda functions** are anonymous (or nameless) functions. This means that they can be applied without having an explicit declaration, i.e. the **function declaration and application are merged into one**. Similar to normal functions, the syntax for lambda functions includes its arguments and a function body that specifies how the result is calculated. However, instead of using a name for the function, we use the backslash symbol `"\"` (similar to the Greek letter lambda – λ), and instead of the equality symbol, we use the function arrow `"->"`:

```haskell
\<ARGUMENT1> <ARGUMENT2> -> <FUNCTION BODY>
```

We can directly use lambda functions just like any other function, so here is how we could use our `triple` function as a lambda function:

```haskell
ghci> (\x -> x * 3) 4
12
```

Lambda functions are very useful for functions that are only used locally because we can simplify our code. For example, our previously defined function `trackScore` could be improved by using a lambda function to calculate the score:

```haskell
trackScore4 :: Float -> Float -> String
trackScore4 time avgTime
  | time < avgTime = "Great! Your time is " ++ show (score) ++ " 
      seconds below average!"
  | time > avgTime = "Your time is " ++ show (score) ++ " seconds 
      above average."
  | otherwise = "Your time is on par with the average time!"
    where
      score = (\x y -> abs (x - y)) time avgTime
```


# Function Operators

Sometimes our code can become difficult to read when using a large number of parentheses. This usually happens when we want to apply multiple functions to the same arguments and we use parentheses to determine how we want to apply those functions. For example, imagine a simple function that determines whether the square of an integer is greater than 100 with the use of helper functions `square` and `gt100`:

```haskell
square :: Int -> Int
square x = x * x

gt100 :: Int -> Bool
gt100 x = x > 100

squareGt100 :: Int -> Bool
squareGt100 x = gt100 (square x)
```

Because we are applying both `gt100` and `square` functions to the same argument, we can compose them into one and avoid parentheses altogether by applying that composed function to the argument. This is achieved through two function operators, **function composition** and **function application** operators:

1\) The **function composition operator** is `(.)`, and it is simply another function that returns a composed function as its result. This is how it is defined in the Prelude:

```haskell
(.) f g = \x -> f (g x)
```

It takes in two functions and returns a nameless lambda function that applies both functions to an argument, so it composes two functions into one. Note that the **function composition associates to the right**, i.e. the function on the right will be applied first, and then the function on the left will be applied to the result.

2\) The **function application operator** is `($)`, and it simply applies the given function to the given argument. This is how it is defined in the Prelude:

```haskell
f $ x = f x
```

We can use function composition in the definition of the `squareGt100` function:

```haskell
squareGt100 :: Int -> Bool
squareGt100 x = gt100 . square $ x
```

That is, we first compose the two functions, `gt100` and `square` and then apply the composed function to the argument `x`. Note that we could also use just the function composition operator, but in that case, we would still have to use parentheses:

```haskell
squareGt100 :: Int -> Bool
squareGt100 x = (gt100 . square) x

ghci> squareGt100 9
False
ghci> squareGt100 11
True
```


# List Comprehensions

In this chapter, we introduce **list comprehensions**, which are used to create new lists from existing ones. The term comes from mathematics, where *set comprehension* is used to describe a set by enumerating its elements and/or stating conditions its members must satisfy. In Haskell, the syntax is the following:

```haskell
[ <GENERATOR> | <ELEMENT> <- <LIST>, <GUARD> ]
```

The `GENERATOR` is an expression that specifies how the elements of the new lists should be calculated, the `ELEMENT` is an element from the specified existing `LIST`, and the `GUARD` is **an optional condition** we can set that an `ELEMENT` must satisfy to end up in the new list we are creating via the `GENERATOR` expression. The whole line can be read as *"create a list by applying the `GENERATOR` for each `ELEMENT` of the `LIST` that meets the criteria set by the `GUARD`"*. Let's take a look at an example list comprehension that creates **a list of only even numbers**:

```haskell
ghci> [x | x <- [1..10], even x]
[2,4,6,8,10]
```

The above can be read as *"create a list of all numbers `x` such that `x` is an element of the list `[1..10]` and `x` is an even number"*. This simply puts `x` into a new list if it meets the guard criteria, but we could also apply function(s) to `x`:

```haskell
ghci> [x * 2 | x <- [1..10], even x]
[4,8,12,16,20]
```

We do not even have to use `x` for our generator, while we can still use it for the guard expression:

```haskell
ghci> ["even!" | x <- [1..10], even x]
["even!","even!","even!","even!","even!"]
```

We can also specify **multiple lists as well as multiple guards in list comprehensions**. In the case of multiple lists, the deeper nested list (the one specified last) is iterated through for each element of the previous list(s):

<pre class="language-haskell"><code class="lang-haskell">ghci> [ (x, y) | x &#x3C;- [1..3], y &#x3C;- ['a'..'c'] ]
[
<strong>    (1,'a'),(1,'b'),(1,'c'),
</strong>    (2,'a'),(2,'b'),(2,'c'),
    (3,'a'),(3,'b'),(3,'c')
]
</code></pre>

In this case, the list `['a'..'b']` is iterated through three times, once for each element in the first list `[1..3]`.


# Introduction

A **higher-order function** in Haskell is a function that either takes in a function as its argument or returns a function as its result. We have already seen how functions can return other functions as their result when we introduced [curried functions](/types-in-haskell/function-types/curried-functions), so we will focus on **functions that take other functions as arguments** in this chapter. First, let's look at a simple example of a higher-order function that takes in a function and applies it twice to an argument:

```haskell
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

ghci> applyTwice (++ " two") "one"
"one two two"
```

The function we passed in `(++ "two ")` simply appends the string `"two "` to the argument passed in (in this case, it must be a string), and it is applied twice when the higher-order function `applyTwice` is called.

Now let's take a closer look at two higher-order functions that are defined in the Prelude for working with lists, `map` and `filter`.


# The map Function

The `map` function takes in a function and a list, and applies the given function to each element of that list. As we have seen how list comprehensions work in the previous chapter, we could define `map` as:

```haskell
map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]
```

Note that the type variables `a` and `b` in the function definition could represent the same type, but this definition gives us flexibility so that a function passed in that takes in one type (`a`) can return another type (`b`), in which case we end up with a list of the type `[b]`. For example, we can pass our function `squareGt100` to a list of numbers and end up with a list of booleans:

```haskell
ghci> map squareGt100 [7..12]
[False, False, False, False, True, True]
```

Here are some other examples of using `map` with other pre-defined functions:

```haskell
ghci> map (* 2) [1..5] -- multiply each number in the list by 2
[2, 4, 6, 8, 10]

ghci> map not [True, False] -- not function reverses the boolean value
[False, True]

ghci> map reverse ["Cardano", "ADA"] -- reverse a given list (strings are lists of chars)
["onadraC","ADA"]

ghci> map ("Hi, " ++) ["Joe", "Jan"]
["Hi, Joe","Hi, Jan"]
```


# The filter Function

The `filter` function is another higher-order function for working with lists. As the name suggests, it is used for filtering lists by selecting **only elements that satisfy a predicate** defined by the function passed in. Like `map`, we could also define filter using a list comprehension:

```haskell
filter :: (a -> Bool) -> [a] -> [a]
filter f xs = [x | x <- xs, f x]
```

Unlike `map`, the `filter` function must receive a function that returns a boolean as its argument, and the resulting list from `filter` will always be of the same type as the list we passed in because we are only selecting elements from that list, rather than generating new ones. We can `filter` a list using our `squareGt100` function from before in order to get the elements for which `squareGt100` returns `True`:

```haskell
ghci> filter squareGt100 [7..12]
[11,12]
```

Here are some other examples of using `filter` with other pre-defined functions:

```haskell
ghci> filter odd [1..5] -- get all odd numbers from a list
[1,3,5]

ghci> filter (\x -> length x > 2) ["a", "abc"] -- elements with length greater than 2
["abc"]

ghci> filter (\(x:xs) -> x == 'a') ["cardano", "ada"] -- elements staring with 'a'
["ada"]
```


# Introduction

In programming, we often want to repeat the same action multiple times, and this concept is called **looping**. Imperative languages have syntax for defining loops in their programs (usually in forms of `for` and `while`), and programming without loops is almost unimaginable. However, in Haskell, there is no such syntax for loops, and the **basic mechanism for looping is recursion**.

**Recursive functions** are those that are **defined in terms of themselves**, i.e. the function body includes a call to the function itself. This means that a function can call itself over and over again without stopping, creating an infinite loop. So when we define recursive functions, we usually include a special pattern that, when matched, does not call the function anymore but returns some value instead. This pattern is called **the base case**, while patterns that do call the function again are called **recursive cases**. Let's consider a simple function that calculates the sum of all natural numbers up to `n`:

```haskell
sumN :: Int -> Int
sumN 0 = 0                -- base case
sumN x = x + sumN (x - 1) -- recursive case
```

That is, the sum of all natural numbers up to zero is simply zero, and for any other integer `x`, it can be defined as the number `x` plus the sum of all natural numbers up to `x - 1`. Let's take a closer look at what the actual execution looks like:

```haskell
sumN 4
= 4 + sumN 3
= 4 + 3 + sumN 2
= 4 + 3 + 2 + sumN 1
= 4 + 3 + 2 + 1 + sumN 0
= 4 + 3 + 2 + 1 + 0       -- the base case stops further looping
10
```

Recursion is very powerful in Haskell when it is combined with lists. In fact, the `map` function we defined with a list comprehension is actually defined using recursion in the Prelude:

```haskell
map _ [] = []
map f (x:xs) = f x : map f xs
```

Like before, we have a base case in which we do not care about the function that is passed to map as the list it is supposed to operate on is empty and we simply return `[]`. The recursive case, however, applies the function `f` to `x` (the head of the list) and joins the result with the result of the recursive call on the remainder of the list (the tail of the list).


# 4 Steps to Defining Recursive Functions

A good set of steps to follow when defining recursive functions is:

1. **Define the function type**

   Thinking about function types is very helpful when defining functions, and explicitly

   defining the function type is good practice.
2. **Enumerate different cases**

   Considering the general cases we expect allows us to create the function structure that we can then fill out gradually. For example, two standard cases for lists are empty and non-empty lists.
3. **Take care of the simple cases first (usually base cases)**

   The simple cases are usually straightforward so it's easier to define them. For example, our

   `sumN 0 = 0` is a simple case and also the base case.
4. **Define the other cases**

   Here, we have to think about how to calculate the wanted result using both the recursive call

   on the function itself and any other functions we might need. For example, in `sumN x = x sumN (x - 1)` we used both the `(+)` and `(-)` functions.


# Recursion Practice

Let's practice recursion by defining some more recursive functions:

* A function that takes two positive integers, `x` and `y` and **raises `x` to the power of `y`** :
  1. **Define the type**

     We know the function will take two integers and return an integer.

     ```
     power :: Int -> Int -> Int
     ```
  2. **Enumerate different cases**

     We can think of two special cases, where either of the arguments is zero, and the general case where both are greater than zero.

     ```
     power _ 0 =
     power 0 _ = 
     power x y =
     ```
  3. **Take care of the simple cases first (usually base cases)**

     Any number to the power of zero is equal to one. Note that we set this pattern first

     because we want to consider zero to the power of zero to be equal to one. The other simple case is that zero to the power of any other number (other than zero itself) is equal to zero.

     ```
     power _ 0 = 1
     power 0 _ = 0
     ```
  4. **Define the other cases**

     Now, we get to the recursive case. We can define that `x` to the power of `y` is equal to `x`

     multiplied by the result of the recursive call to the function with `(y - 1)`

     ```
     power x y = x * power x (y - 1)
     ```

{% hint style="info" %}
For practice, write out how this function would be applied step by step. &#x20;
{% endhint %}

* A function that takes in a list and **returns a new list with only the even-indexed** **elements** (with the first element considered odd-indexed):
  1. **Define the type**

     We know the function will take in a list of some type and return a list of the same type.

     ```
     evens :: [a] -> [a]
     ```
  2. **Enumerate different cases**

     Here, we have to think about the cases we can have. The first one is very simple, if the supplied list is empty, we should return an empty list, but we will leave the definitions for what to return for the next step. The next case we can consider is a list with only one element. We are then left with the general case of two or more elements in a list.

     ```
     evens [] = 
     evens [_] = 
     evens (_ : x : xs) = 
     ```
  3. **Take care of the simple cases first (usually base cases)**

     In the first case (empty list) we already mentioned that we just want to return an empty list. The case with just one element in the list should also return an empty list as that element is odd-indexed and we are only interested in even-indexed elements.

     ```
     evens [] = []
     evens [_] = []
     ```
  4. **Define the other cases**

     That last case we laid out is where the list has two or more elements. In this case, we should ignore the first element, take the second one and join it with the result of the recursive call of the remaining list.

     ```
     evens (_ : x : xs) = x : evens xs
     ```

{% hint style="info" %}
For practice, write out how this function would be applied step by step. &#x20;
{% endhint %}


# Folds

A **fold** or a **folding function** is a higher-order function that processes a data structure (e.g. a list) in some order and builds a return value along the way. Therefore, a fold needs three things to work - **a function that combines the elements, a starting value, and the data structure** where the elements are stored.

There are two basic folding functions defined in the Haskell Prelude, `foldr` and `foldl`. The difference between them is the order in which they apply the combining function to the elements.


# Fold Right (foldr)

The `foldr` function associates the combining function to the right, i.e. the right-most elements of the data structure will be evaluated first. Let's take a look at its definition using recursion on lists:

```haskell
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
```

The starting value `v` is used to complete the folding once we get to the end of the list. Otherwise, we would be missing one last argument and get a curried function as a result instead of the value we are looking for. The case of a non-empty list is handled by simply applying the function `f` to the head of the list, and the recursively processed tail (as we know the function `f` takes in two arguments). Two simple examples of folding would be calculating the sum and product of a list:

```haskell
sum :: Num a => [a] -> a
sum xs = foldr (+) 0 xs
```

Where `(+)` is our combining function and `0` is the starting value. The application would look like this:

```haskell
sum [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0))
6
```

Here, it is clear that the function application associates to the right. We can also see that the application of `foldr` can be thought of as replacing the cons operator in the list with our combining function (in this case the addition operator):

```haskell
[1, 2, 3]
1 : (2 : (3 : [])) -- list construction
1 + (2 + (3 + 0))  -- foldr (+)
```

And to define a function that calculates the product of a list using `foldr`:

```haskell
product :: Num a => [a] -> a
product = foldr (*) 1
```

In this case, our starting value is `1` instead of `0` as we are dealing with multiplication and not addition. Also, note that we have taken `xs` out of the definition from both sides of the equation – this is called **eta reduction** and is used to simplify functions. It takes advantage of the partial application of functions so that the function product now returns a curried version of `foldr` that takes in one final argument (the data structure) to be completely applied. It is important to note that the type of the function does not change in its reduced form.

```haskell
product [1, 2, 3]
1 * (foldr (*) 1 [2, 3])
1 * (2 * (foldr (*) 1 [3]))
1 * (2 * (3 * (foldr (*) 1 [])))
1 * (2 * (3 * 1))
6
```


# Fold Left (foldl)

In `foldl`, the combining function (or operator) associates to the left, meaning the left-most elements will be evaluated first, i.e. the most nested parentheses will be on the left side of the data structure. Therefore, its definition using recursion on lists would be:

```haskell
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
```

So we take the second argument `v` and the head of the list `x` and apply the combining function on them, and then use that result to feed the recursive function for the rest of the list. The sum of a list using `foldl` would be applied like this:

```haskell
foldl (+) 0 [1, 2, 3]
foldl (+) (0 + 1) [2, 3]
foldl (+) ((0 + 1) + 2) [3]
foldl (+) (((0 + 1) + 2) + 3) []
(((0 + 1) + 2) + 3)
```

Notice that the places of the accumulator value `v` are switched in `foldl` relative to `foldr` in the combining function `f`. That is, in `foldr`, the first argument of the combining function is an element from the data structure, while in `foldl`, the first argument is the accumulator value and the second one is the element of the data structure. This may not be clear from the examples of `sum` and `product`, so let's implement a folding function that calculates the length of a list with both `foldr` and `foldl` using a lambda function as the combining function:

```haskell
lengthr :: [a] -> Int
lengthr = foldr (\_ n -> n + 1) 0  -- list element first, accumulator second
ghci> lengthr [1, 2, 3]
3
```

If we want to declare the same function with `foldl`, we have to reverse the arguments for the combining function to avoid a type error:

```haskell
lengthl :: [a] -> Int
lengthl = foldl (\n _ -> n + 1) 0  -- accumulator first, list element second
Prelude> lengthl [1, 2, 3]
3
```


# Declaring Types

We have already explored the basic types of Haskell in [Basic Types](/types-in-haskell/basic-types), so now we will look into how we can define our own types. There are three different ways in which we can define new types in Haskell – **Type synonyms** (or **Type aliases**), **Data declarations**, and **Newtype declarations**.


# Type Synonyms

**Type synonyms** are the simplest way to declare a new type as they simply provide an alias for an already existing type. For example, we already know that `String` is actually just a synonym for a list of `Chars`, and it is defined as:

```haskell
type String = [Char]
```

We can use the declared type synonyms to define other types as well. We can define a type for a list of Strings:

```haskell
type StringList = [String]
```

It is important to note that the **type synonyms and their base types are interchangeable** in almost all cases. That means that any function that has a type signature including a list of strings (`[String]`) could be used on an element that has the type of `StringList` as they are just synonyms:

```haskell
reverseStringList :: StringList -> StringList
reverseStringList xs = reverse xs
-- interchangeable types StringList | [String]
reverseStringList :: [String] -> [String]
reverseStringList xs = reverse xs

ghci> reverseStringList ["abc", "123"]
["123","abc"]
```


# Data Declarations

With the keyword `Data`, we can define new types rather than just synonyms for already existing ones. Types declared with `data` are called **algebraic**, referencing **"sum"** and **"product"**. In data types, **"sum"** means *alteration* (`A | B`, meaning `A` or `B` but not both), and **"product"** means *combination* (`A B`, meaning `A` and `B` together).

### Sum-types

For example, we can create a type that represents a card suit:

```haskell
data Suit = Hearts
          | Diamonds
          | Spades
          | Clubs
```

`Suit` is the **type constructor** in this definition, and the values (`Hearts`, `Diamonds`, `Spades` or `Clubs`) are **data constructors**. It states that the new type `Suit` can have **one of the four values** (the `|` symbol stands for "or"). This means that `Suit` is a **sum type**, which is any type that has multiple possible representations. Another example of a sum type would be `Bool` which can be either `True` or `False:`

```haskell
data Bool = True | False
```

**Data constructors** can have zero or more arguments. `Hearts | Diamonds` and `True | False` are examples of data constructors that have zero arguments - **nullary data constructors**. Likewise, **type constructors** can have zero or more arguments. `Suit` and `Bool` are examples of **nullary type constructors**.

Let's take a look at some type- and data- constructors that have more than zero arguments. Here is an example of an error type from the [cardano-node repository](https://github.com/input-output-hk/cardano-node/blob/85d05720da7b0c02dfa890079e568c8499a027a7/cardano-node/src/Cardano/Node/Types.hs#L49-L52):

```haskell
data ConfigError =
    ConfigErrorFileNotFound FilePath
  | ConfigErrorNoEKG
    deriving Show
```

`ConfigError` is a nullary type constructor, and its data constructors are `ConfigErrorFileNotFound FilePath`, and `ConfigErrorNoEKG`. `ConfigErrorFileNotFound FilePath` is a **unary** data constructor meaning that it actually holds some data, in this case of type `FilePath`. Nullary type constructors we have seen so far contain no data aside from their names.

Both the type name and its constructors must begin with a capital letter, and **constructors must be unique** to that type, i.e. the same constructor cannot be defined in more than one type. Once a new type is defined, it can be used in functions just like any other data type in Haskell. To illustrate, a very simple function to get the card suit in a string format using pattern matching would be:

```haskell
suitStr :: Suit -> String
suitStr Hearts = "... of hearts."
suitStr Diamonds = "... of diamonds."
suitStr Spades = "... of spades."
suitStr Clubs = "... of clubs."

ghci> suitStr Hearts
"... of hearts."
```

### Product-types

The `Suit` type is an example of a sum-type. Now let's look at an example of a product-type that combines multiple fields together. We can imagine a rectangle, which has two sides `a` and `b`, and to construct a valid rectangle both of them must be provided. We can define the type as:

```haskell
data Rect = Rect Double Double
    deriving Show
```

In this case, the `Rect` on the left side is the type constructor (nullary), and the `Rect` on the right side is the data constructor (binary as it takes two arguments). To create a valid `Rect` type, both `Double` arguments must be joined together:

```haskell
ghci> a = Rect 2.0 3.0
ghci> a
ghci> Rect 2.0 3.0
```

It is interesting to note that the `Rect` on the right side is a function:

```haskell
ghci> :type Rect
ghci> Rect :: Double -> Double -> Rect
```

This means that even here we can take advantage of partial application:

```haskell
ghci> a = Rect 2.0
ghci> :type a
ghci> a :: Double -> Rect
```

And we can create functions based on the `Rect` type, for example, calculating the rectangle area:

<pre class="language-haskell"><code class="lang-haskell">area :: Rect -> Double
area (Rect a b) = a * b

<strong>ghci> area Rect 2.0 3.0
</strong>ghci> 6.0
</code></pre>

### Field labels (records)

As you can imagine, with product-types that represent more complex things, such as people or any large set of parameters, the definitions might become unclear from just the list of the arguments in the type. For example, imagine a type to define a company. We would need fields for e.g. the company name, its address, year of foundation, number of employees...

```haskell
data Company = Company String String Int Int
```

From the above definition alone, it is hard to intuitively understand which `String` or `Integer` stands for what. A more intuitive way to define complex types is by using the **field labels**:

```haskell
data Company = Company {
    cName :: String,
    cAddress :: String,
    cYear :: Int,
    cNre :: Int
} deriving Show
```

This is much more user-friendly. In addition, by using field labels, we get automatic *getter* functions for individual fields:

```haskell
ghci> c = Company "MyCompany" "25th Street" 1999 26
ghci> cAddress c
"25th Street"
ghci> cYear c
1999
```


# Newtype declarations

A special case of a new type declaration `newtype` can be used **if the type has a single constructor with a single argument**. For example, a type for representing an IP address could be declared this way:

```haskell
newtype IPAddress = IP String
```

The `newtype` is different from `type` because it defines a completely new type rather than just a synonym for an existing type such as:

```haskell
type IPAddress = String
```

So any function that requires an `IPAddress` declared as a `newtype` will only work with that type, and not simply a `String` type.

When compared to `data`, the `newtype` has some efficiency benefits because it states that `IPAddress` is simply a wrapper for the value of an existing type `String`, whereas the data declaration:

```haskell
data IPAddress = IP String
```

states that `IPAddress` is a completely new data type.


# Introduction

**Classes** in Haskell are used to ensure that certain **methods** (functions) are supported by any type that is an instance of the given `Class` (in other words, belongs to the given class). We can think of classes as **collections of types that support the operations of that class**. Let's explore the basic built-in classes in Haskell to get a better idea.


# Basic Classes


# Eq – Equality Types

The `Eq` class supports the **comparison methods** (equality and inequality), so any two values of a type that is an instance of the `Eq` class can be compared using the functions:

```haskell
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
```

We have already used these functions many times, and we were able to because all the basic types (`Char`, `Bool`, `Int`....) are instances of the `Eq` class. Classes are defined using the `class` keyword followed by the **class name**, the **type specification** and the `where` keyword, followed by the **default definitions** of the class methods:

```haskell
class Eq a where
  (==), (/=) :: a -> a-> Bool
  
    -- Minimal complete definition:
    -- (==) or (/=)
    
  x /= y = not (x == y)
  x == y = not (x /= y)
```

We see the two default methods above defined in terms of each other, which means we need to define one of them in a clear way to have a complete definition for an instance. For example, the `Bool` type can be made an instance of the `Eq` class with:

```haskell
instance Eq Bool where
  False == True = False
  True == False = False
  _ == _ = True
  
-- or using the (/=) method
    
instance Eq Bool where
  False /= True = True
  True /= False = True
  _ /= _ = False
```

Keep in mind that the definitions of the required functions can be as simple or as complicated as you like, and default definitions can be overwritten when declaring instances.


# Ord – ordered types

The `Ord` class requires any type that wants to be an instance of it to first be an instance of the `Eq` class by using a **class constraint**, and additionally, to support the following methods:

```haskell
class (Eq a) => Ord a where
  (<), (<=), (>), (>=) :: a -> a -> Bool
  min, max :: a -> a -> a
```

In other words, the `Ord` class extends the `Eq` class and supports additional methods `(<)`, `(<=)`, `(>)`, `(>=)`, `min` and `max`. The `min` and `max` methods are defined by default as:

```haskell
min x y
 | x <= y = x
 | otherwise = y
 
max x y
 | x <= y = y
 | otherwise = x
```

And for a minimal definition of the class, we just need to define the `(<=)` method because the other ones also have default definitions:

```haskell
class (Eq a) => Ord a where
  (<), (<=), (>), (>=) :: a -> a -> Bool
  min, max :: a -> a -> a

    -- Minimal complete definition:
    -- (<=)
    
  x < y = x <= y && x /= y
  x > y = y < x
  x >= y = y <= x
  
  min x y
    | x <= y = x
    | otherwise = y
  max x y
   | x <= y = y
   | otherwise = x
```

All the basic types of Haskell are also instances of the `Ord` class.


# Show – Showable Types

The `Show` class is used for types whose values can be represented as strings and support the `show` method. All the basic types of Haskell are also instances of the `Show` class.

```haskell
show :: a -> String

ghci> show False
"False"

ghci> show [1..3]
"[1, 2, 3]"
```


# Read – readable types

The `Read` class supports reading and conversion of string representations of values into actual types using the `read` method. All the basic types of Haskell are also instances of the `Read` class. Note that we sometimes have to specify the type to be read in cases where the intended type cannot be inferred:

```haskell
ghci> read "False"
*** Exception: Prelude.read: no parse

ghci> read "False" :: Bool
False
```

That is, in the first case, the compiler does not know whether to read `"False"` as a type of `String` or `Bool`, so it throws an exception, while in the second case, we explicitly state that we want to read it as a `Bool`. However, if we had some additional boolean function (e.g. negation) to be called on the read argument, the compiler would be able to automatically infer the wanted type:

```haskell
ghci> not $ read "False"
True
```


# Num – Numeric Types

The `Num` class supports basic numeric methods for its types:

```haskell
(+), (-), (*) :: a -> a -> a
negate, abs, signum :: a -> a
```

Notice that division is not included here because of how it is handled differently for integers floating-point numbers, as we will see in the next two classes (`Integral` and `Fractional`). The `signum` method returns the sign of a number (-1 for negative numbers and 1 for positive ones).


# Integral – Integral Types

The `Integral` class extends the `Num` class and supports two additional methods for working with integral numbers, integer division and integer remainder:

```haskell
div, mod :: a -> a -> a

ghci> 5 `div` 3
1

ghci> 5 `mod` 3
2
```

Basic types `Int` and `Integer` are instances of the `Integral` class.


# Fractional – Fractional Types

The `Fractional` class extends the `Num` class and supports two additional methods for working with floating-point numbers, fractional division and reciprocation:

```haskell
(/) :: a -> a -> a
recip :: a -> a

ghci> 5.0 / 2.0
2.5

ghci> recip 10 -- reciprocal is simply 1 / x
0.1
```


# Enum – Enumeration Types

The last class we will look at here is the `Enum` class which supports operations on sequentially ordered types. We have already used this class in `[1..3]` for creating a list of elements from `1` to `3`.

```haskell
class Enum a where
  succ, pred :: a -> a
  toEnum :: Int -> a
  fromEnum :: a -> Int
  enumFrom :: a -> [a] -- [n..]
  enumFromThen :: a -> a -> [a] -- [n, n'..]
  enumFromTo :: a -> a -> [a] -- [n..m]
  enumFromThenTo :: a -> a -> a -> [a] -- [n, n'..m]
```

We do not have to worry about the implementation details of the Enum class at this point, but we can see that with an `Enum` class, we have access to the `[..]` methods which can be very useful.


# Derived Instances

The `deriving` keyword can be used to make a new type into an instance of other built-in classes `Eq`, `Ord`, `Show`, `Read`, and `Enum` without the need for defining any of the methods. For example, the `Bool` type can be declared as:

```haskell
data Bool = False | True
  deriving (Eq, Ord, Show, Read)
```

It is as if we are stating that the new data type `Bool` can have two values (two nullary constructors `True` and `False`) and it should also be made an instance of the classes `Eq`, `Ord`, `Show` and `Read`, but we let the compiler write the actual code for us using the default definitions. Note that for the `Ord` class, the default ordering will be the order in which the constructors are defined – in this case, `True` comes after `False` and is, therefore *"greater than"* `False`. With this definition, we can use methods of all the class instances included with the type `Bool`:

```haskell
ghci> True == True
True

ghci> False < True
True

ghci> show True
"True"

ghci> read "False"
False
```


# Exercise – Making a Card Deck Type

Let's now try to implement a data type that will represent a deck of cards. First, we can think about what type would be fitting for a card deck – a list of cards would be a good representation. But then what type is fitting for a single card? **Each card should have a rank and a suit** so we can make another type for cards that has the type of a tuple `(Rank, Suit)`. Let's start at the lowest level, the `Rank` and `Suit` type. Remember that we already defined the `Suit` type, but we will now also derive the `Show` class for it:

```haskell
data Suit = Hearts
  | Diamonds
  | Spades
  | Clubs
    deriving (Show)
```

which leaves us with the task of defining `Rank` for which we can also use nullary constructors and also derive some built-in classes:

```haskell
data Rank = Deuce
  | Three
  | Four
  | Five
  | Six
  | Seven
  | Nine
  | Ten
  | Jack
  | Queen
  | King
  | Ace
    deriving (Show, Eq, Ord, Enum)
```

We can then already use methods of those classes on the `Rank` type:

```haskell
ghci> Deuce < Three
True

ghci> Deuce <= Three
True

ghci> Deuce == Three
False

ghci> Deuce > Three
False

ghci> [Deuce .. Five]
[Deuce, Three, Four, Five]
```

We have the `Rank` and `Suit` types now, and we can simply define the type of Card as a type synonym for a tuple of `(Rank, Suit)`:

```haskell
type Card = (Rank, Suit)
```

Similarly, we can define a deck of cards as a type synonym for a list of `Card` types:

```haskell
type Deck = [Card]
```

We have all the required types for actually building a deck now, so let's make a function for that purpose. We will use [list comprehension](/list-comprehensions/list-comprehensions) and take advantage of the fact that `Rank` supports [enumeration](/type-classes/basic-classes/enum-enumeration-types):

```haskell
buildDeck :: Deck
buildDeck = [(rank, suit) | rank <- [Deuce .. Ace], suit <- suitList]
  where
    suitList = [Hearts, Diamonds, Spades, Clubs]
```

And we can now build a deck of cards using that function:

```haskell
ghci> deck = buildDeck
ghci> show deck
"[(Deuce, Hearts),(Deuce, Diamonds),(Deuce, Spades),(Deuce, Clubs),
(Three, Hearts),(Three, Diamonds),(Three, Spades),(Three, Clubs),(Four, 
Hearts),(Four, Diamonds),(Four, Spades),(Four, Clubs),(Five, Hearts),
(Five, Diamonds),(Five, Spades),(Five, Clubs),(Six, Hearts),(Six, 
Diamonds),(Six, Spades),(Six, Clubs),(Seven, Hearts),(Seven, Diamonds),
(Seven, Spades),(Seven, Clubs),(Nine, Hearts),(Nine, Diamonds),(Nine, 
Spades),(Nine, Clubs),(Ten, Hearts),(Ten, Diamonds),(Ten, Spades),(Ten, 
Clubs),(Jack, Hearts),(Jack, Diamonds),(Jack, Spades),(Jack, Clubs),
(Queen, Hearts),(Queen, Diamonds),(Queen, Spades),(Queen, Clubs),(King, 
Hearts),(King, Diamonds),(King, Spades),(King, Clubs),(Ace, Hearts),(Ace,
Diamonds),(Ace, Spades),(Ace, Clubs)]"
```


# Introduction

So far, we have only looked at pure programming in Haskell where there is no interaction with the outside world. That being said, we have actually been using an instance of an interactive program, GHCi, which constantly receives some input from us, interprets it, produces a result and then waits for further input. Our programs took their inputs explicitly through the code itself and produced some results. But most of the time, we want to create programs that can interact with the outside world, for example, with users or the computer file system. Those things require side effects by default and are therefore impure, so in this chapter, we will look at how we can make interactive programs in the pure language of Haskell using **input/output actions**.


# Input / Output Actions

Haskell uses a special type `IO` to distinguish impure, input/output actions from pure expressions. The idea of the `IO` type is that apart from returning some value, it may also interact with the outside world along the way. The `IO` type has the following structure:

```haskell
IO a
```

where `IO` is the type name, and `a` is the parameterised value that it returns. For example:

```haskell
IO Int -- an action that returns an Int
IO () -- an action that returns an empty tuple, called a unit
```

The last example `IO ()` represents an action that is run solely for its side effects and simply returns an empty tuple (a void value or *unit*). Some **basic actions** in Haskell are:

```haskell
getChar :: IO Char       -- reads and returns a character from the screen
putChar :: Char -> IO () -- prints a character to the screen
return  :: a -> IO a     -- returns a value as an action
```

Note that, strictly speaking, `putChar` and `return` are not actions, but functions that return actions. The `return` function is simply our one-way bridge from the pure world to the impure world that we use when we want to use pure values in actions, which we will see in examples soon. For now, let's just try out the basic actions `getChar` and `putChar` in GHCi:

```haskell
ghci> getChar
1'1'            -- input is 1

ghci> getChar
'\n'


ghci> putChar 'a'
a

ghci> putChar '\n'

```


# Sequencing Actions

Sometimes, we want to perform a sequence of actions one after the other. This can be easily done using the **do notation** in Haskell, which is used to create one composite action from two or more individual actions in the `do` block. The general structure of the `do` notation is the following:

```haskell
do value1 <- action1
   value2 <- action2
   ...
   return (value1, value2...)
```

We can read it as *"perform `action1` that will generate the value `value1`, then perform the next action `action2` to generate the value `value2` and so on. In the end, return the tuple of generated values as a type `IO`".* The `return` function is just another **action** in the sequence (remember that `return` is a function by itself but when applied to an argument it returns an action). That means that we **do not have to use `return` at the end of the `do` block**.

We also **do not have to use the generator arrow** if we do not intend to use the result value from a particular action. For example, to write a simple `"Hello World"` program using do notation, we can use the `putStrLn` function, which prints a string to the screen and a new line character at the end of it:

```haskell
hello :: IO ()
hello = do
  putStrLn "Hello"
  putStrLn "World!"
  
ghci>hello
Hello
World!
```


# Exercise - Numbers Guessing Game

Now that we know more about **actions** in Haskell, let's implement a number-guessing game between two players. The idea of this game is very simple and involves two players. The first player thinks of a number that must be hidden and the second player tries to guess it. If the guess is correct, the game ends, otherwise, the program outputs whether the wanted number is higher or lower than the guess, and asks for another guess.

We start by defining the high-level definition of the game itself in `Numbers.hs` which will have the type `IO ()`:

```haskell
numbers :: IO ()
numbers = do
  putStrLn "Think of a number: "
  number <- getSecretNumber
  putStrLn "Guess the number: "
  play number
```

Now, we just have to define our helper functions `getSecretNumber` and `play`. `getSecretNumber` should do two things. Firstly, it should only allow valid numbers (in our case integers) to be read, and secondly, it should not allow the entered number to be visible on the screen. Let's start with the first requirement and implement a `getInt` function – we have to tell Haskell that we want to read a line, but also that we must get a type `Int` out of it:

```haskell
getInt :: IO Int
getInt = do
  number <- getLine
  return (read number :: Int)
```

We use `getLine` to get input from the user, i.e. a string that is submitted once the new line character is entered, rather than just a single character as with `getChar`. And then, remember the [`Read` class](/type-classes/basic-classes/read-readable-types)? We know `Int` is an instance of the `Read` class so we can use the `read` method to read a `String` from `getLine` as an `Int`. We use the `:: Int` to explicitly state that we want to read an `Int` from the input. If that's not possible, we will get an exception, which is okay for now.

```haskell
ghci> getInt
10
10

ghci> getInt
abc
*** Exception: Prelude.read: no parse
```

As is, this function `getInt` can be used for guessing, but not for entering the number to be guessed. Now, for the second requirement, we must ensure that both the entering of a number is hidden when being entered. So we will also use the `hSetEcho` from the `System.IO` library to prevent printing to the screen while we read the number in our `getSecretNumber` function:

```haskell
getSecretNumber :: IO Int
getSecretNumber = do
  hSetEcho stdin False
  number <- getInt
  hSetEcho stdin True
  return number
```

Now, we have everything we need to define the `play` function, which represents the main game loop:

```haskell
play :: Int -> IO ()
play number = do
  putStr "? "
  guess <- getInt
  if | guess == number ->
         putStrLn "That's correct!"
     | guess > number ->
         do
           putStrLn "Too high!"
           play number
     | otherwise ->
         do
           putStrLn "Too low!"
           play number
```

We first ask for the guess and then use a [`MultiWayIf` ](/defining-functions-working-with-functions/conditionals/multiwayif)to decide what to print out and whether the game is finished. Don't forget that we must add the `{-# LANGUAGE MultiWayIf #-}` to the top of our `Numbers.hs` file for this to work. In the case of an incorrect guess, we print whether it is too high or too low and recursively call `play` again with the same secret number:

```haskell
ghci> numbers
Think of a number:
Guess the number:
? 9
Too low!
? 11
Too high!
? 10
That's correct!
```


# Introduction

In this chapter, we explore the more advanced topics of Haskell - **functors, applicative functors** and **monads*****.*** These three concepts are [type classes](/type-classes/introduction) in Haskell that generalise ideas of **function mapping**, **function application** and **programming with effects**, respectively.


# Functors

**Functors** generalise the idea of **function mapping** on a data structure type, i.e. applying a function to each element in the data structure. We have looked at the `map` function that does exactly that but is limited to a specific data structure - `list`. However, any **parameterised** **type** (data structure) can be made into an instance of the `functor` class so that it supports function mapping to its elements through the use of the `fmap` function:

```haskell
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  
  -- Minimal complete definition:
  -- fmap
```

{% hint style="info" %}
The `(<$)` function simply replaces all elements in the data structure with the given value `a.`
{% endhint %}

Comparing `fmap` to `map`:

```haskell
map :: (a -> b) -> [a] -> [b]
```

We can see that `fmap` has the exact same type signature as `map` - but`map` is limited to the type of `lists`, whereas `fmap` can be used with any parameterised type that uses a *type constructor*`f`, i.e. is a class of `Functor f`. Note that the form of`[a]` and `[b]` is just syntax sugar for the list type and is equivalent to `[] a` and `[] b` , where `[]` is the *type constructor* for the list type.

Since the `map` and `fmap` functions perform the same action, it is very simple to make the `list` type into a functor (and it is made into one by default) by using the \`instance\` keyword:

```haskell
instance Functor [] where
    -- fmap :: (a -> b) -> [] a -> [] b
    fmap = map
```

However, when it comes to other data structure types, we have to define the `fmap`  function ourselves. For example, the [`Maybe` type](https://wiki.haskell.org/Maybe) (also an instance of the `Functor` class by default) can be made an instance of the `Functor` class as:

```haskell
instance Functor Maybe where
    -- fmap :: (a -> b) -> Maybe a -> Maybe b
    fmap _ Nothing = Nothing
    fmap f (Just x) = Just (f x)
```

In the case of a `Nothing`, we ignore the function and return `Nothing` as `Nothing` generally represents an error state that we want to propagate through our `fmap` function as well. Otherwise, we apply the function `f` to the underlying value `x` of `Just x` and return the `Maybe` type (using the `Just` constructor) of the result, i.e. the function application `f x`.

Now let's see how we can make a newly-defined data type into an instance of the `Functor` class. We will first define a data type `Tree` that will represent a full [**binary tree**](https://en.wikipedia.org/wiki/Binary_tree). A full binary tree is a binary tree type in which every tree node has either `0` or `2` children. In our case, a node with `0` children will be a `Leaf` that stores some value, and a node with `2` children will be a `Branch` that branches into two new nodes without storing a value itself:

```haskell
data Tree a = Leaf a | Branch (Tree a) (Tree a)
    deriving (Show)
```

And now, we want to make `Tree` a functor, so we have to define the `fmap` function for it:

```haskell
instance Functor Tree where
    -- fmap :: (a -> b) -> Tree a -> Tree b
    fmap f (Leaf x) = Leaf (f x)
    fmap f (Branch l r) = Branch (fmap f l) (fmap f r) 
```

The first case of `Leaf` is analogous to how we defined the `Just` case of the `Maybe` functor - we apply the function `f` to the underlying value `x` and return it wrapped in the `Leaf` constructor. In the other case, where we are dealing with a `Branch` we recursively apply `fmap` to both children nodes of the branch.

To represent the following binary tree:

![Example binary tree.](/files/-MXSCF91qRYstPnEBDzZ)

We can use the following code and `fmap` over the entire data structure, applying the specified function (in this case `(/2)`) to each leaf:

```haskell
ghci> myTree = (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 10) (Leaf 20)))
ghci> fmap (/2) myTree

Branch (Branch (Leaf 0.5) (Leaf 1.0)) (Branch (Leaf 5.0) (Leaf 10.0))
```

Note that the `Prelude` comes with an [infix operator](/defining-functions-working-with-functions/the-infix-operator) for `fmap` as well - `(<$>)`, not to be confused with the [function application operator](/defining-functions-working-with-functions/function-operators), `($)`:

```haskell
 ($)  :: (a -> b) -> a -> b
 
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
```

`($)` is the simple function application operator we learned about before, while `(<$>)` is *also a function application operator* but with lifting over a Functor. We could also write the above code as:

```haskell
ghci> myTree = (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 10) (Leaf 20)))
ghci> (/2) <$> myTree

Branch (Branch (Leaf 0.5) (Leaf 1.0)) (Branch (Leaf 5.0) (Leaf 10.0))
```

## Functor Laws

There are two functor laws that must be satisfied to ensure that `fmap` works as intended:

```haskell
fmap id = id
```

The `id` is the identity function, and it is used to simply return the unaltered argument passed in. This means that mapping the `id` function over a structure should return the same structure back unaltered.

```haskell
fmap (g . f) = fmap g . fmap f
```

The second functor law ensures that *function* *composition* is preserved when using `fmap` so that it does not matter whether we map a composed function `(g . f)` or map the first function `g` and then the second function `f`, as long as the order of the `g` and `f` functions stays the same.


# Applicative Functors

The missing functionality of functors is obvious - `fmap` only works for functions that take in exactly 1 argument and apply that function to each individual element of a given data structure. But we might want to apply a function that takes **multiple arguments** - for example, how can we add together two values of the `Maybe` type? We could write our own function specific to that need:

```haskell
maybeAdd :: Maybe Int -> Maybe Int -> Maybe Int
maybeAdd (Just x) (Just y) = Just (x + y)
maybeAdd _ _ = Nothing

ghci> maybeAdd (Just 5) (Just 3)
Just 8
```

But that way we would have to write a new custom-made function for every function we would like to apply to two (or more) `Maybe` types - for example, multiplication.

This is where **Applicative Functors** (or **Applicatives**) come into play. Applicatives generalise applying pure functions to **effectful** **arguments** (such as the `Maybe` type) instead of plain values. The definition of `Applicative` is:

```haskell
class (Functor f) => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
    
  -- Minimal complete definition:
  -- pure, (<*>)
```

Firstly, for a type to become an instance of `Applicative`, it must be an instance of the `Functor` class. The `pure` method is used to transform arbitrary values into the functor data structure `f a`. The `(<*>)` method is very similar to that of `fmap` , but in this case, the function being applied is itself wrapped into the functor data structure `f (a -> b)` - this is exactly what allows us to use [currying ](/types-in-haskell/function-types/curried-functions)and apply functions that take an unlimited number of arguments on `Applicative` data instances.

### The Maybe Applicative

The effect of the `Maybe` type is the possibility of failure, and we will explore the effects of some other data types later. Let's look at how the `Maybe` type is made an instance of the `Applicative` class in the `Prelude`:

```haskell
instance Applicative Maybe where
    pure                  = Just
    (Just f) <*> (Just x) = Just (f x)
    _        <*> _        = Nothing
```

`pure` wraps a value with the `Just` constructor, and `(<*>)` applies the function to the value if neither of the arguments has failed, otherwise, it results in `Nothing`. Now we can simply calculate the sum of two `Maybe` types without the need for defining a function:

```haskell
ghci> pure (+) <*> Just 5 <*> Just 3
Just 8
```

We first use `pure` on the addition function `(+)` in order to wrap it into a `Maybe` and then apply it to the two arguments. Let's take a closer look at how the application is executed and keep track of types:

```haskell
-- pure transforms the (+) into an instance of an Applicative
ghci> :t pure (+)
pure (+) :: (Applicative f, Num a) => f (a -> a -> a)

ghci> :t pure (+) <*> Just 5
pure (+) <*> Just 5 :: Num a => Maybe (a -> a)
-- <*> applies the (+) function (wrapped into a Maybe) to the first argument
-- it returns a curried function wrapped in the Maybe constructor

ghci> :t pure (+) <*> Just 5 <*> Just 3
pure (+) <*> Just 5 <*> Just 3 :: Num b => Maybe b
-- finally, the curried function is applied to the second argument
-- and the addition is complete and results in a Maybe b
```

The final result is of the type `Maybe b` so the underlying **effect** of the `Maybe` type - the possibility of failure - is handled by the applicative style of function application. In other words, we do not have to define any additional functions to handle specific `Nothing` cases, as they are already defined in the `Applicative` instance definition for `Maybe`:

```haskell
ghci> pure (+) <*> Just 5 <*> Nothing
Nothing

ghci> pure (+) <*> Nothing <*> Just 3
Nothing
```

### The List Applicative

The `List` applicative is implemented in a way that the function application through `(<*>)` applies the function in every possible combination of the arguments (as a Cartesian product in mathematics). So the underlying **effect** of the `List`  type is the possibility of non-deterministic results. The `Applicative` instance declaration for `List` is:

```haskell
instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
```

With that, we can apply functions on `List` types through `(<*>)`:

```haskell
ghci> pure (+) <*> [1,2] <*> [3,4]
[4,5,5,6]
-- 1 + 3
-- 1 + 4
-- 2 + 3
-- 2 + 4

ghci> [(+10), (*10), (^2)] <*> [1,2,3]
[11,12,13,10,20,30,1,4,9]
```

In the second example, each of the functions in the first list is a curried function that takes in one additional argument, and the result of the applicative action is applying all the functions from the first list to all the arguments of the second list.

{% hint style="info" %}
For those curious, there is also an implementation that matches only one argument per function - ZipList (<http://hackage.haskell.org/package/base-4.11.1.0/docs/Control-Applicative.html#t:ZipList>)
{% endhint %}

### The IO Applicative

The `IO` type refers to the impure world of Haskell, and its underlying **effect** is the ability to perform input/output actions. Therefore, the applicative instance of the `IO` type supports the application of pure functions to impure arguments, and can also handle sequencing and extraction of result values:

```haskell
instance Applicative IO where
    pure = return
    a <*> b = do
        f <- a
        x <- b
        return (f x)
```

`pure` is simply our `return` function that wraps a pure value into an `IO` type, and given two impure arguments (`IO` actions), `(<*>)` performs the action `a` to get the function `f` and the action `b` to get the argument `x` , and finally returns `f x` - the result of that function applied to the argument wrapped in the `IO` type.

As was mentioned before, the use of applicative style can handle both **sequencing** and **extraction** of values, so to define a function that reads two lines of characters and returns their concatenation, instead of:

```haskell
read2 :: IO String
read2 = do
    a <- getLine
    b <- getLine
    return (a ++ b)
```

we can simply write:

```haskell
read2 :: IO String
read2 = pure (++) <*> getLine <*> getLine

ghci> read2
Applicative
Functors
"ApplicativeFunctors"
```

Furthermore, it becomes much easier to create a function that reads an arbitrary `n` number of lines and concatenates them using applicative style and [recursion](/recursion/introduction):

```haskell
getLines :: Int -> IO String
getLines 0 = return []
getLines n = pure (++) <*> getLine <*> getLines (n - 1)

ghci> getLines 5
1
2
3
4
5
"12345"
```

### Applicative Laws

There are four laws applicative functors must follow:

```haskell
pure id <*> v = v                            -- Identity
pure f <*> pure x = pure (f x)               -- Homomorphism
u <*> pure y = pure ($ y) <*> u              -- Interchange
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition
```

The `Identity` law states that applying the `id` function to an argument in applicative style returns the unaltered argument, much like we saw in functors.

The `Homomorphism` law states that `pure` preserves function application in the sense that applying a pure function to a pure value is the same as calling `pure` on the result of normal *function application* to that value (`f x`).

The `Interchange` law states that the order in which we evaluate components does not matter in the case when we apply an effectful function to a pure argument. The `($ y)` is used to supply the argument `y` to the function `u`. A simpler example of using `($ y)`:

```haskell
ghci> map ($ 2) [(2*), (4*), (8*)]
[4,8,16]
```

The `Composition` law states that *function composition* `(.)` works with the `pure` function as well, so that `pure (.)` composes functions, i.e. composing functions `u` and `v` with `pure (.)` and applying the composed function to `w` gives the same result as simply applying both functions `u` and `v` to the argument `w`.


# Monads

Let's start by saying that **monads** are difficult to grasp at first. It might take you some time and a couple of attempts to really even start to have an understanding of them, so don't worry if they seem overwhelming at the start.

Like [functors ](/functors-applicatives-and-monads/functors)and [applicatives](/functors-applicatives-and-monads/applicative-functors), **monads** provide an abstraction for chaining operations that allows us to structure our programs generically and avoid code duplication. This abstraction allows us to simplify problems like handling exceptions during execution (which we will explore shortly) by building succinct pipelines without needing to worry about flow control or side effects.

Many types we already encountered as pre-defined in Haskell are also instances of the `Monad` typeclass, including `Maybe` and `List`.


# Maybe Monad

For our next example, let's imagine that we have a database that holds information about accounts and transactions - we don't have to worry about accessing the database right now, we just assume that a given account or transaction either exists in our database or doesn't. We could have the following type defined (using type synonym declarations):

```haskell
type Transaction = [Char] -- or String
type Account = [Char]     -- or String
```

where both the `Transaction` and the `Account` instances are represented by strings (e.g. through a hashing function). Imagine that we now want to create a function that, given a `Transaction`, looks up both the `Account` from which the transaction originated and the destination `Account` in our database. There are three ways in which this function could fail:

1. The transaction is not found in our database
2. The origin account is not found in our database
3. The destination account is not found in our database

From what we already learned, we would write this function as something like this:

```haskell
-- helper functions for finding transactions/accounts that may fail
findTransaction :: Transaction -> Maybe Transaction
findOriginAccount :: Transaction -> Maybe Account
findDestinationAccount :: Transaction -> Maybe Account

findAccounts :: Transaction -> Maybe (Account, Account)
findAccounts t =
    case findTransaction t of
        Nothing -> Nothing
        Just t ->
            case findOriginAccount t of
                Nothing -> Nothing
                Just originAcc ->
                    case findDestinationAccount t of
                        Nothing -> Nothing
                        Just destinationAcc ->
                            Just (originAcc, destinationAcc)
```

{% hint style="info" %}
Is it possible to write this function using [`Applicative`](/functors-applicatives-and-monads/applicative-functors) form?
{% endhint %}

The important thing to notice here is the common pattern of exception checking at every step. At any point that we fail to find an element we are looking for, we want the function to handle this exception by returning `Nothing`, and we implement this very explicitly resulting in long and hard-to-read function code. In other words, every step of the function depends on the result of the previous one (or *"binds"* to the result of the previous one). This is where we can take advantage of the fact that `Maybe` is a monad to simplify this by abstracting the error handling away.

First, let's look at the declaration of the `Monad`class in Haskell:

```haskell
class Applicative m => Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b
    
    return = pure
    
    -- Minimal complete definition:
    -- (>>=), return
```

A `Monad` is therefore an `Applicative` that also supports the two methods, `return` and `(>>=)` (referred to as ***bind***). The `return` method wraps a value of any basic type `a` into the monad, returning a **monadic value**. The built-in declaration also has a default declaration for the `return` function, and it is simply the `pure` method of the underlying `Applicative` class that is used to wrap a value in the applicative constructor. The `(>>=)` method takes a monadic value and a function that returns a monadic value and generally applies that function to the first argument. Let's explore this in more detail with the implementation of the monad class for the `Maybe` type as an example:

```haskell
instance Monad Maybe where
    -- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
    Nothing >>= _ = Nothing
    (Just x) >>= f = f x
```

{% hint style="info" %}
Why don't we wrap the result of the function application `f x` into the `Maybe` type constructor `Just`?
{% endhint %}

For the `return` method, we keep the default declaration of `pure` which simply resolves to the `Just` constructor for the `Maybe` type. The `(>>=)` method exemplifies the main idea of monads, which is that we first look at the impure argument we receive (in this case `Maybe a`) and decide what to do from there. That way, function application depends on the result of the first argument (or the underlying value of the first argument). If `Maybe a` is a `Nothing` then we can completely ignore the function and simply propagate the exception with `Nothing`. Only if we know that the first argument is really a `Just a` do we unwrap the `a` value and apply the function `f` to it.

We can now re-write our `findAccounts` function in a simpler way using the fact that `Maybe` is a monad:

<pre class="language-haskell"><code class="lang-haskell">findAccounts :: Transaction -> Maybe (Account, Account)
<strong>findAccounts t =
</strong>  findTransaction t >>=
    (\tx -> findOriginAccount tx >>=
      (\origin -> findDestinationAccount tx >>=
        (\destination -> return (origin, destination) )))
</code></pre>

That reads much better - we don't have to take care of every `Nothing` possibility as the monadic aspect of `Maybe` takes care of this for us. One thing to note is that the `tx` argument is available at any step below the first "bind" as all the lambda functions bind to one another in a sequence. The same applies to the `origin` argument which we only use in the last step in order to `return` our result.

Does this kind of sequencing remind you of something we saw before? We used the `do` notation with [I/O actions](/interactive-programming/sequencing-actions) to perform multiple actions in a sequence. As it turns out, the `do` notation is not specific to I/O actions but is actually just an alternative monad syntax and can be used with any monad. We can therefore re-write `findAccounts` using `do` notation:

<pre class="language-haskell"><code class="lang-haskell">findAccounts :: Transaction -> Maybe (Account, Account)
<strong>findAccounts t =
</strong>  do
    tx          &#x3C;- findTransaction t
    origin      &#x3C;- findOriginAccount tx
    destination &#x3C;- findDestinationAccount tx 
    return (origin, destination)
</code></pre>

This now looks much more like an imperative language and we could say it actually is, but with the imperative language being written is the `Maybe` language, which supports exceptions. `findTransaction`, `findOriginAccount` and `findDestinationAccount` are all statements in the imperative language of the `Maybe` monad. And this extends to all monads so that a value of type `M a` is interpreted as a statement in an imperative language of `M` , with the semantics of that language being determined by the underlying monad `M` .


# List Monad

As we already mentioned in the [Applicatives](/functors-applicatives-and-monads/applicative-functors#the-list-applicative) section, the underlying effect of the `List` type is support for *non-deterministic* computations. `Maybe` computations can return either `Nothing` or a `Just` value, while `List` computations can return zero, one or multiple values based on their length. Let's see how this is defined in the `Monad` instance of `List`:

```haskell
instance Monad [] where
   -- return :: a -> [a]
   return x = [x]
   
   -- (>>=)  :: [a] -> (a -> [b]) -> [b]
   m >>= f  = [y | x <- m, y <- f x]
```

{% hint style="info" %}
The bind operator in this case is defined using [list comprehension](/list-comprehensions/list-comprehensions). Can you define it using the functions [`map`](/higher-order-functions/the-map-function) and [`concat`](http://zvon.org/other/haskell/Outputprelude/concat_f.html)?
{% endhint %}

The `return` method simply takes a value `x` and puts it into a `List` structure `[x]`. The `(>>=)` method for lists extracts all the values `x` from the list `m` and applies the function `f` to each of them, combining all the results in one final list. As with the [`Maybe` monad](/functors-applicatives-and-monads/monads/maybe-monad), the bind operator,  allows us to chain operations together with lists as well. With lists, these chaining operations will combine all output possibilities in a single result list.

Let's take a look at a simple example of chaining list operations together. Imagine we want to model [mitosis](https://en.wikipedia.org/wiki/Mitosis), a process where a single cell divides into two identical daughter cells. First, we create a function `mitosis` that simply splits a cell in two:

```haskell
mitosis :: String -> [String] -- we will represent cells with simple strings
mitosis = replicate 2

ghci> ["Cell"] >>= mitosis
["Cell", "Cell"]
```

With the monadic instance of lists, we have a simple way of chaining multiple operations on lists. We can chain the result of multiple cell replications starting with one cell into one final list:

```
ghci> ["Cell"] >>= mitosis >>= mitosis >>= mitosis
["Cell", "Cell", "Cell", "Cell", "Cell", "Cell", "Cell", "Cell"]
```

In this case, the `mitosis` function is applied to each element of the list, providing a resulting list to be passed to the subsequent functions.

The monadic instance of lists also allows us to use the [do notation](/interactive-programming/sequencing-actions):

```haskell
threeGens :: String -> [String]
threeGens gen0 = do
        gen1 <- mitosis gen0
        gen2 <- mitosis gen1
        gen3 <- mitosis gen2
        return gen3
        
ghci> threeGens "Cell"
["Cell", "Cell", "Cell", "Cell", "Cell", "Cell", "Cell", "Cell"]
```


# Monad Laws

There are three laws that monad instances must satisfy to be valid:

* Left Identity ->  `(return x) >>= f = f x`

The left identity law states that if we simply use `return` on a value before binding it to the function `f`, the result should be the same as simply applying `f x` directly.

* Right Identity -> `m >>= return = m`

The right identity law states that if have some monadic value `m` (or an expression that computes to this monadic value) and bind it to the `return` function, the result should be simply the same value `m`.

* Associativity -> `(m >>= f) >>= g = m >>= (\x -> f x >>= g)`

The associativity law states that if have some monadic value `m` and want to create a chain binding for functions `f` and `g` (applying `f` first, and the result of that application to `g`), then it should not matter whether we nest the two binding functions, as long as the order of application is preserved.


# References / Further Reading

* Programming in Haskell by Graham Hutton - <https://www.cs.nott.ac.uk/~pszgmh/pih.html>
* Ohaskell guide (in Russian) - <https://www.ohaskell.guide/>
* Learn You A Haskell - <http://learnyouahaskell.com/>
* learn4Haskell - <https://github.com/kowainik/learn4haskell>
* Yet Another Haskell Tutorial - <https://en.wikibooks.org/wiki/Yet_Another_Haskell_Tutorial>
* HaskellWiki - <https://wiki.haskell.org/Haskell>
* Haskell WikiBook - <https://en.wikibooks.org/wiki/Haskell>
* What I Wish I Knew When Learning Haskell - [http://dev.stephendiehl.com/hask/](http://dev.stephendiehl.com/hask/#why-are-monads-confusing)
* Wikipedia pages - <https://en.wikipedia.org/wiki/Monad_(functional_programming)>
* University of Pennsylvania Haskell course - <https://www.cis.upenn.edu/~cis1940>
* Haskell course by Dmitrii Kovanikov - <https://github.com/haskell-beginners-2022/course-plan>