Composing an endofunction with itself

Suppose we are given an endofunction $f : \mathcal{X} \to \mathcal{X}$. Let us introduce a new function $f^{(n)}$, where $n \geq 0$, which we define recursively as follows

$f^{(k)} = f \circ f^{(k-1)}, \qquad{} f^{(0)} = \text{id}$

where $\text{id} : \mathcal{X} \to \mathcal{X}$ is the identity function on $\mathcal{X}$, i.e., $\text{id} (x) = x$ for all $x \in \mathcal{X}$. In Haskell, it is easy to create a higher-order function compose that composes an endofunction $f$ with itself $n$ times:

compose :: (a -> a) -> Integer -> (a -> a)
compose f 0 = (\x -> x)
compose f k = f . (compose f (k-1))

where the identity function is defined anonymously. If you happen to dislike anonymity in your functions, here is another implementation:

compose :: (a -> a) -> Integer -> (a -> a)
compose f 0 = identity
compose f k = f . (compose f (k-1))

identity :: a -> a
identity x = x

There are many other alternatives. Take a look at this Stack Overflow thread. I particularly liked Reid Barton‘s elegant solution using a right-fold:

compose f n = foldr (.) id (replicate n f)

where id = (\x -> x). Beautiful, isn’t it? If this one-liner does not convert you to Haskell, then nothing will.

__________

Example

Let $\mathbb{Z}_{64} := \{0, 1,\dots,63\}$, and let function $f$ be defined by

$\begin{array}{rl} f : \mathbb{Z}_{64} &\to \mathbb{Z}_{64}\\ n &\mapsto n+1 \pmod{64}\end{array}$

This function corresponds to a cyclic shift. Therefore, we expect to have $f^{(64)} = \text{id}$. Let $g := f^{(32)}$ and $h := f^{(64)}$. We load the script above into GHCi, and voilà, we have the session:

*Main> let ns = [0..63]
*Main> let f =  (\n -> (n+1) mod 64)
*Main> map f ns
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,
17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,
33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,
49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,0]

So far, so good! Let us take a look at $g$ and $h$:

*Main> let g = compose f 32
*Main> let h = compose f 64
*Main> map g ns
[32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31]
*Main> map h ns
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63]

Indeed, as we expected, we have $f^{(64)} = \text{id}$.

__________

Everything in this post is elementary. But now that the elements are solid, we can dare to attempt more sophisticated things. Like what? Like composing lists of (distinct) functions. I am thinking of permutations. I am thinking of perfect shuffles.

One Response to “Composing an endofunction with itself”

1. Rod Carvalho Says:

Here’s a bit of equational reasoning:

compose f 3 = f . (compose f 2)
= f . (f . (compose f 1))
= f . (f . (f . (compose f 0)))
= f . (f . (f . identity))