# Rod Carvalho

## Posts Tagged ‘Folding’

### Function composition via folding

December 2, 2012

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

$\text{compose} \,\, [f_0, f_1, \dots, f_{n-1}] = f_0 \circ f_1 \circ \dots \circ f_{n-1}$

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 $n$ 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 $n$ 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`.

Tags:Folding, Function Composition, Haskell, Higher-Order Functions
Posted in Haskell | 3 Comments »
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 3, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8877004384994507, "perplexity_flag": "head"}