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.

About these ads

Tags: Folding, Function Composition, Haskell, Higher-Order Functions