Function composition via folding

Let us suppose that we are given a list of functions. We would like to compose the functions in this list (if they are composable, of course) in the order in which they are arranged in the list, i.e., we would like to create a higher-order function compose such that

Here is one of many possible implementations in Haskell:

compose :: [(a -> a)] -> (a -> a)
compose = foldr (.) (\x -> x)

where we use a right-fold to compute the composition. Note that the identity function is defined anonymously. What happens if we apply compose to the empty list? We should obtain the identity function. Let us see if this is the case:

compose [] = foldr (.) (\x -> x) [] = (\x -> x)

Indeed, it is the case: if we apply compose to the empty list, we obtain the identity function. What is the type of this identity function? We load the two-line script above into GHCi and experiment a bit:

*Main> let id = compose []
*Main> :t id
id :: a -> a
*Main> map id [0..9]
[0,1,2,3,4,5,6,7,8,9]
*Main> map id ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"

We thus obtain a polymorphic identity function that merely outputs its input, regardless of the type of the input. So far, so good. What happens if we apply compose to a non-empty list? Here is some more equational reasoning:

compose [f0,f1,f2] = foldr (.) (\x -> x) [f0,f1,f2]
                   = foldr (.) (\x -> x) (f0 : f1 : f2 : [])
                   = f0 . (f1 . (f2 . (\x -> x)))

A couple of days ago, we saw how to compose a function with itself times. This is a special case of composing a list of functions, of course. Using function replicate, we can compose a function f with itself  times in the following manner:

compose (replicate n f) = foldr (.) (\x -> x) (replicate n f)

as suggested by Reid Barton. Let us now repeat the experiment we did perform a couple of days ago, but using the new compose:

*Main> let f =  (\n -> (n+1) `mod` 64)
*Main> let h = compose (replicate 64 f)
*Main> map h [0..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,
 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]

In the next posts, we will do some interesting things with this compose.

Composing an endofunction with itself

Suppose we are given an endofunction . Let us introduce a new function , where , which we define recursively as follows

where is the identity function on , i.e., for all . In Haskell, it is easy to create a higher-order function compose that composes an endofunction with itself 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 , and let function be defined by

This function corresponds to a cyclic shift. Therefore, we expect to have . Let and . 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 and :

*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 .

__________

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.