Functional Composition with Multiple Parameters in Haskell

CompositionWithMultipleParameters.md

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 f1 f2 = (f1 . ) . f2

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.

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

This is Haskell's left section.

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

This is Haskell's right section.

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

This is the normally infixed operator in prefix notation.

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

This is an example of factoring out a parameter.

(f . (g x)) = ((f . ) . g) 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.

((f . ) . g) x = (f . (g 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:

f1 :: (a -> b)
f2 :: (a -> b -> c)

So f1 takes 1 parameter and f2 takes 2 parametes.

And p1 and p2 are parameters.

Now we want to call f2 with 2 parameters and then apply the results to f1. 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.

So we start with a lambda of the function we want:

\f1 f2 p1 p2 -> f1(f2 p1 p2)

Then factor out p2 using rule #5:

\f1 f2 p1 p2 -> (f1 . (f2 p1)) p2

Then eta reduce (cancel p2):

\f1 f2 p1 -> (f1 . (f2 p1))

Factor out p2 using rule #5 again:

\f1 f2 p1 -> ((f1 . ) . f2) p1

Eta reduction (cancel p1):

\f1 f2 -> ((f1 .) . f2)

This is my original compose2 function!

Continuing, we rewrite prefixed using rule #4:

\f1 f2 -> (.) (f1 .) f2

Eta reduction (cancel f2):

\f1 -> (.) (f1 .)

Rewrite prefixed using rule #4:

\f1 -> (.) ((.) f1)

Factor out f1 using rule #5:

\f1 -> ((.) . (.))f1

And finally, one last eta reduction:

(.) . (.)

Therefore:

\f1 f2 -> ((f1 .) . f2) = (.) . (.)

What about more parameters

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 about other combinations

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.