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.
First, knowing some rules will help.
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))
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.
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) = (.) . (.)
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.
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.