### Overview

In this chapter you’ll learn how to write and run simple Haskell programs. You’ll also learn about some of the most important pieces of Haskell’s syntax, and get some hands on experience with how Haskell differs from other languages you might have used.

### Factorials

The factorial function is a simple function that you can define
recursively. You can compute the factorial of a number, `n`

, by
multiplying all of the numbers up to `n`

. For example:

`5 = 5 * 4 * 3 * 2 * 1 = 120 factorial `

Try implementing your own `factorial`

function. You can
test your implementation in `ghci`

and compare its output to the example:

```
λ factorial 1
1
λ factorial 3
6
λ factorial 5
120
λ factorial 10
3628800
λ factorial 25
15511210043330985984000000
```

### Hints

## Click to reveal

Remember that a recursive function needs both a *base case* that tells the
function to stop calling itself, and a *recursive case* where the function calls
itself with a smaller value.

The *base case* for your factorial function is when the number you are
calculating is less than, or equal to, one.

## Click to reveal

In the *recursive case* of your function, you need to multiply the current
number by the *next smallest factorial*.

## Click to reveal

You can solve this problem using either `if`

expressions or *guards*

## Click to reveal

Imagine that we’d use parentheses in the `factorial`

example. We might have
written it like this:

`5 = 5 * (4 * (3 * (2 * 1))) factorial `

Think about what function would represent the value inside of each set of parentheses.

### Solution

## Click to reveal

You can implement this function using either an `if`

expression or a
guard. We’ll look at both solutions, starting with the solution that uses an
`if`

expression.

The first thing we need to do is write our function and define our base case. We’ll leave the rest of the function undefined for the moment:

```
=
factorial n if n <= 1
then 1
else undefined
```

Technically speaking, *factorial* is only defined for positive numbers. We
haven’t yet learned how to prevent users from passing in negative numbers, so
we’ll fall back to defensive programming practices and just check for any number
less than or equal to one. If our number is small enough, we’ll return the
smallest factorial number: one.

What about for a larger factorial? In that case we need to multiply the current
number by the *next smallest* factorial. What’s the value of the next smallest
factorial? We can find it out using the `factorial`

function:

```
=
factorial n if n <= 1
then 1
else n * factorial (n - 1)
```

As you can see in this example, the “next smallest factorial” is our recursive
call to `factorial`

with the next smallest value, `n - 1`

.

If you prefer guards, you’ll notice that the implementation with them is nearly identical:

```
factorial n| n <= 1 = 1
| otherwise = n * factorial (n - 1)
```

### The Fibonacci Sequence

The fibonacci sequence is a sequence of numbers that can be defined
recursively. The first 10 numbers of the fibonacci sequences are:
0,1,1,2,3,5,8,13,21,34. You can calculate any given fibonacci number,
`n`

, by adding up the two previous fibonacci numbers.

Write a function that will compute the nth fibonacci number for any given
number, n. You can test your implementation in `ghci`

and compare it to the
example:

```
λ fibonacci 0
0
λ fibonacci 1
1
λ fibonacci 5
5
λ fibonacci 10
55
λ fibonacci 25
75025
```

### Hints

## Click to reveal

There are *two* cases where the example `fibonacci`

function isn’t recursive:

- The 0th fibonacci number is 0
- The 1st fibonacci number is 1

## Click to reveal

The recursive case of `fibonacci`

needs to make *two* recursive calls, because
it needs to add the next *two* smallest fibonacci values.

### Solution

## Click to reveal

You can implement the `fibonacci`

function using either `if`

expressions or
guards. We’ll use guards in this solution.

The definition of `fibonacci`

is similar to the `factorial`

that you should have
created in the previous exercise. Let’s take a look:

```
fibonacci n| n <= 0 = 0
| n == 1 = 1
| otherwise = fibonacci (n - 1) + fibonacci (n - 2)
```

Once again, you’ll notice that we’re being a bit generous with our smallest base
case. We’re checking for numbers *less than or equal to* zero so that we can
give a sensible answer even if the user passes in a negative number.

In the next base case, we check to see if our value is `1`

. If so, we just
return `1`

. These two base cases let use get the sequence started with the first
two numbers:

```
0 = 0
fibonacci 1 = 1 fibonacci
```

In the next step, `n`

is `2`

. This is a recursive case, and we’re going to look
back both one step to `n = 1`

and two steps to `n = 0`

:

```
2 = fibonacci (2 - 1) + fibonacci (2 - 2)
fibonacci = fibonacci 1 + fibonacci 0
= 1 + 1
= 1
```

Let’s follow up one more time, just to make sure we have the pattern down.

```
3 = fibonacci (3 - 1) + fibonacci (3 - 2)
fibonacci = fibonacci 2 + fibonacci 1
= (fibonacci (2 - 1) + fibonacci (2 - 2)) + 1
= (fibonacci 1 + fibonacci 0) + 1
= (1 + 0) + 1
= 1 + 1
= 2
```

Remember, when you’re working with recursive functions, try to walk through the recursion manually if you’re having trouble understanding how the function works.

## Manual Currying

You’ve learned about how Haskell functions work by taking a single argument. One way to write a function that takes multiple arguments is to pass in a tuple of arguments. For example, consider this addition function:

```
=
uncurriedAddition nums let
= fst nums
a = snd nums
b in a + b
```

Haskell’s standard library includes two functions,
`curry`

and `uncurry`

, that make
it easy for you to convert between functions that take two arguments and
functions that take a tuple. The `curry`

function
transforms a function like our `uncurriedAddition`

function and turns it into one that takes two separate arguments. For example:

```
λ addition = curry uncurriedAddition
λ addOne = addition 1
λ addTwo = addition 2
λ addOne 1
2
λ addOne 2
3
λ addOne 3
4
λ addTwo 1
3
λ addTwo 2
4
λ addTwo 3
5
```

Similarly, the `uncurry`

function takes a regular
function with two arguments and converts it into a function that accepts a
tuple. For example, using `uncurry`

we could have
rewritten `uncurredAddition`

like this:

`= uncurry (+) uncurriedAddition `

Using what you’ve learned in this chapter, try implementing your own version of
`curry`

and `uncurry`

.

Since the standard library already has functions named
`curry`

and `uncurry`

, you should
select different names for your implementations. After you’ve written your
versions, compare the behavior to the standard library implementations to ensure
that your versions behave the same way.

### Hints

## Click to reveal

Remember that functions can be passed around as ordinary arguments. For example,
imagine that we have a function called `addNumbers`

that adds two numbers:

`= a + b addNumbers a b `

Next, we could write a function `callWithTwoArguments`

that takes a function,
and the two arguments that we should call that function with, and returns the
results:

`= f a b callWithTwoArguments f a b `

Finally, we can pass `addNumbers`

to `callWithTwoArguments`

like any other
value. As an example:

`= callWithTwoArguments addNumbers 3 5 addThreeAndFive `

As you’re working on this exercise, remember that you can pass the functions that you want to curry, or uncurry, just like you’d pass around any other argument.

## Click to reveal

Remember that you can get the first element of a tuple using the `fst`

function,
and you can get the second element of a tuple using the `snd`

function:

```
fst ("hello", "haskell")
λ "hello"
snd ("hello", "haskell")
λ "haskell"
```

## Click to reveal

The built-in `curry`

turns a function that takes a tuple into a function that
takes two arguments. Let’s look at an example. Imagine that we have a function
that adds two numbers from a tuple:

`= fst tuple + snd tuple addTuple tuple `

We can test this out in `ghci`

and see that it works just like we’d expect.

```
1,2)
λ addTuple (3
```

If we use `curry`

, we can call this like an ordinary function. We can either use
curry and pass arguments all in one call:

```
curry addTuple 1 2
λ 3
```

Or we can use `curry`

to define a new version of the function that takes two
non-tuple arguments:

```
= curry addTuple
λ addTwo 1 2
λ addTwo 3
3 4
λ addTwo 7
```

The `uncurry`

function works the same way, but it converts functions in the
other direction. For example:

```
uncurry addTwo (1,2)
λ 3
= uncurry addTwo
λ addTuple' 2,3)
λ addTuple' (5
```

You can use these examples as you are testing your own implementation.

### Solution

## Click to reveal

Let’s start by defining our own version of `curry`

called `exampleCurry`

. Our
function will need to take three arguments:

`f`

is a function that takes in a tuple and returns a value`a`

is a value; it’s the first value in the tuple we’ll pass to`f`

`b`

is a value; it’s the second value in the tuple we’ll pass to`f`

It’s easiest to write this function as a one-liner:

`= f (a,b) exampleCurry f a b `

In this code, we’re taking three arguments as input. We’re calling our first argument, the function we want to curry, using a tuple made up of the next two arguments.

If we use this function in `ghci`

we can see it behaves like you’d expect:

```
= fst tuple + snd tuple
λ addTuple tuple 1 2
λ exampleCurry addTuple 3
```

Just like with the `curry`

function defined for us in `Prelude`

, we can use
`exampleCurry`

to create a new function:

```
= exampleCurry addTuple
λ addTwo 1 2
λ addTwo 3
2 3
λ addTwo 5
```

This might be a bit surprising, since you’re still getting used to
Haskell. Remember that Haskell makes it easy for us to do *partial
application*. We could have written `addTwo`

without partial application by
taking in the two arguments that we should call the curried function with:

```
= exampleCurry addTuple a b
λ addTwo a b 1 2
λ addTwo 3
2 3
λ addTwo 5
```