# Twice and thrice

Here is a fun little riddle about higher order functions in Haskell that I discovered today.
Consider the following function `twice`

which takes a function `f`

and applies it twice in a row.

```
twice :: (a -> a) -> a -> a
twice f = f . f
-- Equivalently: twice f x = f (f x)
```

In order for this to make sense (a.k.a. to typecheck), the result of the function `f`

should be eligible as an argument for the very same.
This is to say that the type of the function `f`

should be `a -> a`

for some `a`

.

So far so good, now let’s take the first step towards the riddle. What does the following evaluate to?

```
(twice . twice) (+1) 0
```

First of all, mentally typecheck all function applications in the expression, then try to reason about it conceptually. If you cannot figure it out, don’t worry. We can always unfold definitions:

```
(twice . twice) f x = twice (twice f) x
= ((twice f) . (twice f)) x
= (twice f) (twice f x)
= (twice f) (f (f x))
= f (f (f (f x)))
```

Each equation corresponds to unfolding either the definition of `.`

or `twice`

.
So indeed, `twice . twice`

applies a function four times and for our example above we get `4`

as a result.

This is where the fun starts:

```
(twice twice) (+1) 0
```

I simply left out the `.`

operator, so instead of composing `twice`

with itself we apply `twice`

to itself.
However, by the very definition of `twice`

we have:

```
twice twice = twice . twice
```

To see this, substitute `twice`

for `f`

in its definition and realize that the type `(a -> a) -> a -> a`

is a valid instantiation of the type `a -> a`

!
So without any further thinking, we conclude that `(twice twice) (+1) 0`

also equals `4`

.

## All good things come in threes

Why not have a function that applies a function three times too?
Let us call it `thrice`

.

```
thrice :: (a -> a) -> a -> a
thrice f = f . f . f
-- Equivalently: thrice f x = f (f (f x))
```

And naturally we wonder how this thing behaves when applied to or composed with itself. Namely, what are the values of the following two expressions:

```
(thrice . thrice) (+1) 0
(thrice thrice) (+1) 0
```

Note that the types of `thrice`

and `twice`

are exactly the same, so these expressions typecheck just as before.
The question is what they compute.
Try to figure it out yourself, the next paragraph contains the solution.

## The answer

Instead of writing really complicated and long sentences, I will write some of the corresponding equations and let you do the wording in your own thoughts.

```
(thrice . thrice) f x = thrice (thrice f) x
= thrice (\y -> f (f (f x))) x
= f (f (f (f (f (f (f (f (f x))))))))
```

For our example this shows that `(thrice . thrice) (+1) 0 = 9`

.
To solve the second one we apply the definition of `thrice`

to itself, just like with `twice`

.

```
(thrice thrice) f = thrice (thrice (thrice f))
```

Note that this is what we had above for composition, but wrapped in another `thrice`

call.
So we really have the function which applies `f`

nine times and pass this into `thrice`

,
thus applying `f`

a total of `27`

times!
In the example we get `(thrice thrice) (+1) 0 = 27`

.

If we understand `twice`

as the number two and `thrice`

as three, then what really happens is that `.`

multiplies its arguments while applying one to the other corresponds to computing the power (exponentation).
This connection is actually rather deep and will appear later in the lecture.