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.