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
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
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
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
All good things come in threes
Why not have a function that applies a function three times too?
Let us call it
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
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.
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
(thrice thrice) f = thrice (thrice (thrice f))
Note that this is what we had above for composition, but wrapped in another
So we really have the function which applies
f nine times and pass this into
f a total of
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.