{{ message }}

Instantly share code, notes, and snippets.

anttikuuskoski/CompositionWithMultipleParameters.md

Last active May 4, 2021
Functional Composition with Multiple Parameters in Haskell

Functional Composition with Multiple Parameters in Haskell

In the past, I've written composition functions in both Elm and Haskell that take multiple parameters for the leftmost function, i.e. the function that gets applied first.

(All examples here are in Haskell)

Here was my Haskell implemenation (stolen from the web):

```compose2 :: (c -> d) -> (a -> b -> c) -> a -> b -> d
compose2 g f = (g . ) . f```

Then John Soo from Orange Combinator meetup showed me the `point-free` version:

```compose2 :: (c -> d) -> (a -> b -> c) -> a -> b -> d
compose2 = (.) . (.)```

And we struggled for longer than I'd like to admit trying to understand how these were equal.

I attempted to factor my original but wasn't able to since I didn't understand how to do math with composition very well. But after many failures, I finally realized how to do it.

This document is to capture that process so I'll never forget and to help others who may be struggling on how to do this.

Some simple rules

First, knowing some rules will help.

Composition equivalences

This is the definition of composition.

`g . f = g(f) -- rule #1`

This is Haskell's `left section`.

`(g . ) f = g . f -- rule #2`

This is Haskell's `right section`.

`( . f) g = g . f -- rule #3`

This is the normally `infixed` operator in `prefix` notation.

`(.) g f = g . f -- rule #4`

This is an example of factoring out a parameter.

`(g . (f x)) = ((g . ) . f) x -- rule #5`

It's NOT intuitive. So working backward, i.e. apply `x` on the right side to get the left side may make it more intuitive.

`((g . ) . f) x = (g . (f x))`

Eta Reduction

Here's an example of a function that has redundant parameter definitions:

`g = (\x y -> f x y)`

Function `g` is a function of 2 parameters that first takes an `x` then a `y` and then calls a function `f` which also first takes and `x` then a `y`.

That means that `g` and `f` are the equivalent and therefore can be the same function.

A `Point-free` version of this would be:

`g = f`

Eta Reduction is the process of producing a `Point-free` version of a function.

I like to look at `Eta Reduction` in functional programming as a `cancel on the right` rule.

Let's start with our original redundant version of `g`:

`g = (\x y -> f x y)`

Here `y` is the rightmost term on both sides of the equation and therefore we can cancel it:

`g = (\x -> f x)`

We now have the same situation with `x` and can cancel again:

`g = f`

Take the a slightly more complex function:

`\x y z -> f y x z`

Here `z` is the rightmost term on both sides of the equation and therefore we can cancel it:

`\x y -> f y x`

Notice that we have `y` as the rightmost on the left side but we have `x` on the rightmost side on the right.

So we can no longer reduce this.

Derivation of (.) . (.)

Imagine that:

```g :: (c -> d)
f :: (a -> b -> c)```

So `g` takes 1 parameter and `f` takes 2 parametes.

And `p1` and `p2` are parameters.

Now we want to call `f` with 2 parameters and then apply the results to `g`. This is ALMOST what the `.` operator does. The only difference is we'd like a composition of the 2 functions where it initially wants 2 parameters instead of 1.

`\g f p1 p2 -> g(f p1 p2)`

Then factor out `p2` using rule #5:

`\g f p1 p2 -> (g . (f p1)) p2`

Then eta reduce (cancel `p2`):

`\g f p1 -> (g . (f p1))`

Factor out `p2` using rule #5 again:

`\g f p1 -> ((g . ) . f) p1`

Eta reduction (cancel `p1`):

`\g f -> ((g .) . f)`

This is my original compose2 function!

Continuing, we rewrite prefixed using rule #4:

`\g f -> (.) (g .) f`

Eta reduction (cancel `f`):

`\g -> (.) (g .)`

Rewrite prefixed using rule #4:

`\g -> (.) ((.) g)`

Factor out `g` using rule #5:

`\g -> ((.) . (.))g`

And finally, one last eta reduction:

`(.) . (.)`

Therefore:

`\g f -> ((g .) . f) = (.) . (.)`

We now know:

```compose :: (b -> c) -> (a -> b) -> a -> c
compose1 = .

compose2 :: (c -> d) -> (a -> b -> c) -> a -> b -> d
compose2 = (.) . (.)```

Upon inspection, we can say that `compose1` is 1 compose function and `compose2` is 2 compose functions, composed.

Maybe `compose3` is just 3 compose functions, composed.

We can try in `ghci` to see what we get:

``````λ> :type (.) . (.) . (.)
(.) . (.) . (.)
:: (b -> c) -> (a2 -> a1 -> a -> b) -> a2 -> a1 -> a -> c
``````

This is exactly what we want. So we can write `compose3` like:

```compose3 :: (d -> e) -> (a -> b -> c -> d) -> a -> b -> c -> e
compose3 = (.) . (.) . (.)```

This pattern continues on:

```compose4 :: (e -> f) -> (a -> b -> c -> d -> e) -> a -> b -> c -> d -> f
compose4 = (.) . (.) . (.) . (.)```

Given:

```f4 :: a -> b -> c -> d -> e
f4 w x y z =
-- some implementation```

We can use `compose4` like:

`f1 `compose4` f4`

So far, our leftmost function only takes 1 parameter. But...

What if we wanted to write:

`f2 `compose2` f2a`

where `f2` and `f2a` both take 2 parameters.

For the first time, our leftmost function takes 2 parameters. What does this even mean?

Let's start with `compose2` and add to it until we get a fully applied function, which will be equivalent to `f2 `compose2` f2a`.

```(.) . (.)                                -- compose2
\f2 -> ((.) . (.)) f2                    -- add f2
\f2 -> ((.) . ((.) f2))                  -- apply f2
\f2 -> (.) (f2 . )                       -- write as left section
\f2 f2a -> (.) (f2 . ) f2a               -- add f2a
\f2 f2a -> ((f2 . ) . f2a)               -- infixed

\f2 f2a p1 -> ((f2 . ) . f2a) p1         -- add p1
\f2 f2a p1 -> (f2 . ) (f2a p1)           -- apply p1
\f2 f2a p1 -> f2 . (f2a p1)              -- apply (f2a p1)
\f2 f2a p1 p2 -> (f2 . (f2a p1)) p2      -- add p2
\f2 f2a p1 p2 -> f2 (f2a p1 p2)          -- apply p2
\f2 f2a p1 p2 p3 -> f2 (f2a p1 p2) p3    -- add p3```

Our final function takes 3 parameters. This makes sense if we just think for a moment about:

`f2 `compose2` f2a`

`f2a` takes 2 parameters and then is passed to `f2` which wants 2 parameter, 1 of which is the output of `f2a`. So 2 functions that want 2 parameters each is 4 total.

But the output of `f2a` is an input to `f2` so we only need 3 other parameters.

Therefore:

`f2 `compose2` f2a :: (c -> d -> e) -> (a -> b -> c) -> a -> b -> d -> e`

From this work we can predict:

`f2 `compose3` f3`

Total number of parameters is 5 but 1 is provided by the output of the right function, i.e. `f3`. Therefore, this takes 4 parameters.

Dare we venture here?

What happens when we add more than one compose? For example:

`f2 `compose3` (f2a `compose2` f2b)`

`f2`, `f2a` and `f2b` all take 2 parameters.

We know that the parenthetical takes 3 parameters and f2 takes 2 and we sum them and subtract 1 which means the whole thing takes 4 parameters.

If we apply `p1`, `p2`, `p3`, `p4`, in this order, to this function, which parameters gets passed to which functions?

`f2b` gets the first 2, i.e. `p1` and `p2`. `f2a` gets the output of `f2b` and then the next parameters, i.e. `f2b p1 p2` and `p3`. `f2` gets the output of `f2a` and then the last parameter, i.e. `f2a (f2b p1 p2) ` and `p4`.

So it's:

`f2 (f2a (f2b p1 p2) p3) p4`

Parametric consumption goes from right to left as usual, but there are more of them than traditional composition.