# Composition

Posted on 2018-02-19 by nbloomf

This post is literate Haskell; you can load the source into GHCi and play along.

{-# LANGUAGE NoImplicitPrelude #-}
module Composition
( compose2on1, compose3on1
, compose1on2, compose2on2
, compose1on3
, compose1on4
, _test_compose, main_compose
) where

import Testing
import Functions
import Flip

We can think of $$\compose(f)(g)(x)$$ as taking an outer function $$f$$ of one argument, and another function $$g$$ that massages some input $$x$$ before passing it on to $$f$$. We can express more complicated compositions of functions by stacking $$\compose$$ on itself in various ways – but to avoid keeping track of too many $$\compose$$s it will be handy to generalize to some named operators. Say $$f$$ takes two arguments; a generalized compose for such a function might take two different input-massaging functions $$g$$ and $$h$$, and two inputs $$x$$ and $$y$$, and pass $$g(x)$$ and $$h(y)$$ to $$f$$, like $\Theta(f)(g)(h)(x)(y) = f(g(x))(h(y)).$ We can do exactly this with $$\composeBonA$$.

We define $\composeBonA : (C \rightarrow D \rightarrow E) \rightarrow (A \rightarrow C) \rightarrow (B \rightarrow D) \rightarrow A \rightarrow B \rightarrow E$ by $\composeBonA = \flipC(\compose(\compose(\compose(\compose)))(\compose))$

compose2on1 :: (c -> d -> e) -> (a -> c) -> (b -> d) -> a -> b -> e
compose2on1 = flip3 (compose (compose (compose compose)) compose)

$$\composeBonA$$ does what we want:

When the signatures of $$f$$, $$g$$, and $$h$$ make sense, we have $\composeBonA(f)(g)(h)(x)(y) = f(g(x))(h(y)).$

We have $\begin{eqnarray*} & & \composeBonA(f)(g)(h)(x)(y) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#def-compose2on1} = & \flipC(\compose(\compose(\compose(\compose)))(\compose))(f)(g)(h)(x)(y) \\ & \href{/posts/arithmetic-made-difficult/Flip.html#thm-flip3} = & \compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h)(y) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(\compose))(\compose(f))(g)(x)(h)(y) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose)(\compose(f)(g))(x)(h)(y) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(f)(g)(x))(h)(y) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(f(g(x)))(h)(y) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & f(g(x))(h(y)) \end{eqnarray*}$ as claimed.

_test_compose2on1
:: (Equal e)
=> a -> b -> c -> d -> e
-> Test ((c -> d -> e) -> (a -> c) -> (b -> d) -> a -> b -> Bool)
_test_compose2on1 _ _ _ _ _ =
testName "compose2on1(f)(g)(h)(x)(y) == f(g(x))(h(y))" $\f g h x y -> eq (compose2on1 f g h x y) (f (g x) (h y)) Generalizing further, $$\composeConA$$ acts on a function of three arguments. We define $\begin{eqnarray*} \composeConA & : & (D \rightarrow E \rightarrow F \rightarrow G) \\ & & \rightarrow (A \rightarrow D) \\ & & \rightarrow (B \rightarrow E) \\ & & \rightarrow (C \rightarrow F) \\ & & \rightarrow A \rightarrow B \rightarrow C \rightarrow G \end{eqnarray*}$ by $\composeConA = \flipD(\flipE(\flipC(\compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose)))))$ In Haskell: compose3on1 :: (d -> e -> f -> g) -> (a -> d) -> (b -> e) -> (c -> f) -> a -> b -> c -> g compose3on1 = flip4 (flip5 (flip3 ( compose (compose (compose (compose (compose compose)))) (compose (compose (compose compose)) (compose)) ))) And $$\composeConA$$ does what we want. Whenever the signatures of $$f$$, $$g$$, $$h$$, and $$k$$ make sense, we have $\compose3(f)(g)(h)(k)(x)(y)(z) = f(g(x))(h(y))(k(z)).$ We have $\begin{eqnarray*} & & \composeConA(f)(g)(h)(k)(x)(y)(z) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#def-compose3on1} = & \flipD(\flipE(\flipC(\compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose)))))(f)(g)(h)(k)(x)(y)(z) \\ & \href{/posts/arithmetic-made-difficult/Flip.html#thm-flip4} = & \flipE(\flipC(\compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose))))(f)(g)(h)(x)(k)(y)(z) \\ & \href{/posts/arithmetic-made-difficult/Flip.html#thm-flip5} = & \flipC(\compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose)))(f)(g)(h)(x)(y)(k)(z) \\ & \href{/posts/arithmetic-made-difficult/Flip.html#thm-flip3} = & \compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose))(f)(g)(x)(h)(y)(k)(z) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(\compose(\compose(\compose))))(\compose(\compose(\compose(\compose)))(\compose)(f))(g)(x)(h)(y)(k)(z) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(\compose(\compose)))(\compose(\compose(\compose(\compose)))(\compose)(f)(g))(x)(h)(y)(k)(z) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(\compose))(\compose(\compose(\compose(\compose)))(\compose)(f)(g)(x))(h)(y)(k)(z) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose)(\compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h))(y)(k)(z) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h)(y))(k)(z) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h)(y)(k(z)) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(\compose))(\compose(f))(g)(x)(h)(y)(k(z)) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose)(\compose(f)(g))(x)(h)(y)(k(z)) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(f)(g)(x))(h)(y)(k(z)) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(f)(g)(x)(h(y))(k(z)) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & f(g(x))(h(y))(k(z)) \end{eqnarray*}$ as claimed. _test_compose3on1 :: (Equal g) => a -> b -> c -> d -> e -> f -> g -> Test ((d -> e -> f -> g) -> (a -> d) -> (b -> e) -> (c -> f) -> a -> b -> c -> Bool) _test_compose3on1 _ _ _ _ _ _ _ = testName "compose3on1(f)(g)(h)(k)(x)(y)(z) == f(g(x))(h(y))(k(z))"$
\f g h k x y z -> eq (compose3on1 f g h k x y z) (f (g x) (h y) (k z))

A really good question to ask at this point is, “where on earth did those definitions for $$\composeBonA$$ and $$\composeConA$$ come from?” It’s almost certainly not obvious how we could write such a thing down without already knowing some trick. And there is a trick – it turns out we can calculate these definitions, and others, using the known properties of our function operators. Take $$\composeBonA$$ for example. Say we’re setting out to find a definition for the map $$\Theta(f)(g)(h)(x)(y) = f(g(x))(h(y))$$. First off, I know from experience that (1) with $$\compose$$, we can move function arguments in and out of parentheses as long as they’re in the right order, and (2) putting the arguments of a function in any given order is easy with $$\flip$$ and friends. So we might as well start out looking for $$\Theta$$ such that $\Theta(f)(g)(x)(h)(y) = f(g(x))(h(y)),$ since we can apply an appropriate sequence of $$\flip$$s to $$\Theta$$ at the end.

Now, working backwards, start with $f(g(x))(h(y)).$ Note that this fits the pattern of a $$\compose$$, where the outer function is $$f(g(x))$$, and the inner function is $$h$$. So this expression is equivalent to $\compose(f(g(x)))(h)(y).$ We’ve peeled off the last two arguments of $$\Theta$$ already. We’d like to peel off the next argument from the right; in this case, $$x$$. Imagine that the $$x$$ argument is trapped inside two extra sets of parentheses. And the tool for eliminating parentheses is $$\compose$$. Indeed, we can write $$f(g(x)) = \compose(f)(g)(x)$$, and now $$x$$ is “lifted up” by one level. So our expression is now equivalent to $\compose(\compose(f)(g)(x))(h)(y).$ We can play this game again; $$x$$ is still trapped, and is the argument of a composition where the outer function is $$\compose$$ and the inner function is $$\compose(f)(g)$$. So our expression is equivalent to $\compose(\compose)(\compose(f)(g))(x)(h)(y).$ We can see the trick now; $$g$$ is trapped, and another $$\compose$$ gives $\compose(\compose(\compose))(\compose(f))(g)(x)(h)(y).$ Now $$f$$ is trapped, but another $$\compose$$ gives $\compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h)(y).$ So we have $\Theta = \compose(\compose(\compose(\compose)))(\compose),$ and applying a $$\flipC$$ to this map gives the $$\compose2$$ we defined above.

A similar trick applies when we want to use some input more than once; this time we assume that an appropriate $$\clone$$ has been applied.

Two more generalizations of $$\compose$$ will also be handy.

We define $\composeAonB : (C \rightarrow D) \rightarrow (A \rightarrow B \rightarrow C) \rightarrow A \rightarrow B \rightarrow D$ by $\composeAonB = \compose(\compose)(\compose)$

compose1on2 :: (c -> d) -> (a -> b -> c) -> a -> b -> d
compose1on2 = compose compose compose

And $$\composeAonB$$ behaves like so:

We have $\composeAonB(f)(g)(x)(y) = f(g(x)(y)).$

Note that $\begin{eqnarray*} & & \composeAonB(f)(g)(x)(y) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#def-compose1on2} = & \compose(\compose)(\compose)(f)(g)(x)(y) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\compose(f))(g)(x)(y) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(f)(g(x))(y) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & f(g(x)(y)) \end{eqnarray*}$ as claimed.

_test_compose1on2
:: (Equal d)
=> a -> b -> c -> d
-> Test ((c -> d) -> (a -> b -> c) -> a -> b -> Bool)
_test_compose1on2 _ _ _ _ =
testName "compose1on2(f)(g)(x)(y) == f(g(x)(y))" $\f g x y -> eq (compose1on2 f g x y) (f (g x y)) Now: We define $\composeAonC : (D \rightarrow E) \rightarrow (A \rightarrow B \rightarrow C \rightarrow D) \rightarrow A \rightarrow B \rightarrow C \rightarrow E$ by $\composeAonC = \compose(\compose)(\composeAonB)$ In Haskell: compose1on3 :: (d -> e) -> (a -> b -> c -> d) -> a -> b -> c -> e compose1on3 = compose compose compose1on2 And $$\composeAonC$$ behaves like so: We have $\composeAonC(f)(g)(x)(y)(z) = f(g(x)(y)(z)).$ Note that $\begin{eqnarray*} & & \composeAonC(f)(g)(x)(y)(z) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#def-compose1on3} = & \compose(\compose)(\composeAonB)(f)(g)(x)(y)(z) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\composeAonB(f))(g)(x)(y)(z) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \composeAonB(f)(g(x))(y)(z) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#thm-compose1on2} = & f(g(x)(y)(z)) \end{eqnarray*}$ as claimed. _test_compose1on3 :: (Equal e) => a -> b -> c -> d -> e -> Test ((d -> e) -> (a -> b -> c -> d) -> a -> b -> c -> Bool) _test_compose1on3 _ _ _ _ _ = testName "compose1on3(f)(g)(x)(y)(z) == f(g(x)(y)(z))"$
\f g x y z -> eq (compose1on3 f g x y z) (f (g x y z))

Now:

We define $\composeAonD : (E \rightarrow F) \rightarrow (A \rightarrow B \rightarrow C \rightarrow D \rightarrow E) \rightarrow A \rightarrow B \rightarrow C \rightarrow D \rightarrow F$ by $\composeAonD = \compose(\compose)(\composeAonC)$

compose1on4 :: (e -> f) -> (a -> b -> c -> d -> e) -> a -> b -> c -> d -> f
compose1on4 = compose compose compose1on3

And $$\composeAonD$$ behaves like so:

We have $\composeAonD(f)(g)(x)(y)(z)(w) = f(g(x)(y)(z)(w)).$

Note that $\begin{eqnarray*} & & \composeAonD(f)(g)(x)(y)(z)(w) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#def-compose1on4} = & \compose(\compose)(\composeAonC)(f)(g)(x)(y)(z)(w) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \compose(\composeAonC(f))(g)(x)(y)(z)(w) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \composeAonC(f)(g(x))(y)(z)(w) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#thm-compose1on3} = & f(g(x)(y)(z)(w)) \end{eqnarray*}$ as claimed.

_test_compose1on4
:: (Equal f)
=> a -> b -> c -> d -> e -> f
-> Test ((e -> f) -> (a -> b -> c -> d -> e) -> a -> b -> c -> d -> Bool)
_test_compose1on4 _ _ _ _ _ _ =
testName "compose1on4(f)(g)(x)(y)(z)(w) == f(g(x)(y)(z)(w))" $\f g x y z w -> eq (compose1on4 f g x y z w) (f (g x y z w)) Now: We define $\begin{eqnarray*} \composeBonB & : & (E \rightarrow F \rightarrow G) \\ & & \rightarrow (A \rightarrow B \rightarrow E) \\ & & \rightarrow (C \rightarrow D \rightarrow F) \\ & & \rightarrow A \rightarrow B \rightarrow C \rightarrow D \rightarrow G \end{eqnarray*}$ by $\composeBonB =$ In Haskell: compose2on2 :: (e -> f -> g) -> (a -> b -> e) -> (c -> d -> f) -> a -> b -> c -> d -> g compose2on2 = flip5 (compose compose2on1 compose2on1) And $$\composeBonB$$ behaves like so: We have $\composeBonB(f)(g)(h)(x)(y)(z)(w) = f(g(x)(y))(h(z)(w)).$ Note that $\begin{eqnarray*} & & \composeBonB(f)(g)(h)(x)(y)(z)(w) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#def-compose2on2} = & \flipE(\compose(\composeBonA)(\composeBonA))(f)(g)(h)(x)(y)(z)(w) \\ & \href{/posts/arithmetic-made-difficult/Flip.html#thm-flip5} = & \compose(\composeBonA)(\composeBonA)(f)(g)(h)(x)(z)(y)(w) \\ & \href{/posts/arithmetic-made-difficult/Functions.html#def-compose} = & \composeBonA(\composeBonA(f))(g)(h)(x)(z)(y)(w) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#thm-compose2on1} = & \composeBonA(f)(g(x))(h(z))(y)(w) \\ & \href{/posts/arithmetic-made-difficult/Composition.html#thm-compose2on1} = & f(g(x)(y))(h(z)(w)) \end{eqnarray*}$ as claimed. _test_compose2on2 :: (Equal g) => a -> b -> c -> d -> e -> f -> g -> Test ((e -> f -> g) -> (a -> b -> e) -> (c -> d -> f) -> a -> b -> c -> d -> Bool) _test_compose2on2 _ _ _ _ _ _ _ = testName "compose2on2(f)(g)(h)(x)(y)(z)(w) == f(g(x)(y))(h(z)(w))"$
\f g h x y z w -> eq (compose2on2 f g h x y z w) (f (g x y) (h z w))

## Testing

Suite:

_test_compose ::
( Equal a, Show a, Arbitrary a, CoArbitrary a, TypeName a
, Equal b, Show b, Arbitrary b, CoArbitrary b, TypeName b
, Equal c, Show c, Arbitrary c, CoArbitrary c, TypeName c
, Equal d, Show d, Arbitrary d, CoArbitrary d, TypeName d
, Equal e, Show e, Arbitrary e, CoArbitrary e, TypeName e
, Equal f, Show f, Arbitrary f, CoArbitrary f, TypeName f
, Equal g, Show g, Arbitrary g, CoArbitrary g, TypeName g
) => Int -> Int -> a -> b -> c -> d -> e -> f -> g -> IO ()

_test_compose size cases a b c d e f g = do
testLabel0 "compose"
let args = testArgs size cases

runTest args (_test_compose1on2 a b c d)
runTest args (_test_compose1on3 a b c d e)
runTest args (_test_compose1on4 a b c d e f)
runTest args (_test_compose2on1 a b c d e)
runTest args (_test_compose2on2 a b c d e f g)
runTest args (_test_compose3on1 a b c d e f g)

Main:

main_compose :: IO ()
main_compose = do
_test_compose 1 1 () () () () () () ()