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.

About these ads

Tags: Function Composition, Haskell, Higher-Order Functions

This entry was posted on November 30, 2012 at 21:57 and is filed under Haskell, Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Composing an endofunction with itself”

Rod Carvalho Says:
December 1, 2012 at 08:38 | Reply

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))

Using Reid Barton’s solution instead:

foldr (.) identity (replicate n f) = foldr (.) identity [f,f,f]
                                   = foldr (.) identity (f : f : f : [])
                                   = f . (f . (f . identity))

Rod Carvalho

Composing an endofunction with itself

Like this:

One Response to “Composing an endofunction with itself”

Leave a Reply Cancel reply

Follow “Rod Carvalho”