---
title: Composition
author: nbloomf
date: 2018-02-19
tags: arithmetic-made-difficult, literate-haskell
slug: compose
---
> {-# 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$.
:::::: definition ::
[]{#def-compose2on1}
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))$$
In Haskell:
> compose2on1 :: (c -> d -> e) -> (a -> c) -> (b -> d) -> a -> b -> e
> compose2on1 = flip3 (compose (compose (compose compose)) compose)
::::::::::::::::::::
$\composeBonA$ does what we want:
:::::: theorem :::::
[]{#thm-compose2}
When the signatures of $f$, $g$, and $h$ make sense, we have $$\composeBonA(f)(g)(h)(x)(y) = f(g(x))(h(y)).$$
::: proof ::::::::::
We have
$$\begin{eqnarray*}
& & \composeBonA(f)(g)(h)(x)(y) \\
& \href{@compose@#def-compose2on1}
= & \flipC(\compose(\compose(\compose(\compose)))(\compose))(f)(g)(h)(x)(y) \\
& \href{@flip@#thm-flip3}
= & \compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h)(y) \\
& \href{@functions@#def-compose}
= & \compose(\compose(\compose))(\compose(f))(g)(x)(h)(y) \\
& \href{@functions@#def-compose}
= & \compose(\compose)(\compose(f)(g))(x)(h)(y) \\
& \href{@functions@#def-compose}
= & \compose(\compose(f)(g)(x))(h)(y) \\
& \href{@functions@#def-compose}
= & \compose(f(g(x)))(h)(y) \\
& \href{@functions@#def-compose}
= & f(g(x))(h(y))
\end{eqnarray*}$$
as claimed.
::::::::::::::::::::
::: test :::::::::::
> _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.
:::::: definition ::
[]{#def-compose3on1}
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.
:::::: theorem :::::
[]{#thm-compose3on1}
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)).$$
::: proof ::::::::::
We have
$$\begin{eqnarray*}
& & \composeConA(f)(g)(h)(k)(x)(y)(z) \\
& \href{@compose@#def-compose3on1}
= & \flipD(\flipE(\flipC(\compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose)))))(f)(g)(h)(k)(x)(y)(z) \\
& \href{@flip@#thm-flip4}
= & \flipE(\flipC(\compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose))))(f)(g)(h)(x)(k)(y)(z) \\
& \href{@flip@#thm-flip5}
= & \flipC(\compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose)))(f)(g)(h)(x)(y)(k)(z) \\
& \href{@flip@#thm-flip3}
= & \compose(\compose(\compose(\compose(\compose(\compose)))))(\compose(\compose(\compose(\compose)))(\compose))(f)(g)(x)(h)(y)(k)(z) \\
& \href{@functions@#def-compose}
= & \compose(\compose(\compose(\compose(\compose))))(\compose(\compose(\compose(\compose)))(\compose)(f))(g)(x)(h)(y)(k)(z) \\
& \href{@functions@#def-compose}
= & \compose(\compose(\compose(\compose)))(\compose(\compose(\compose(\compose)))(\compose)(f)(g))(x)(h)(y)(k)(z) \\
& \href{@functions@#def-compose}
= & \compose(\compose(\compose))(\compose(\compose(\compose(\compose)))(\compose)(f)(g)(x))(h)(y)(k)(z) \\
& \href{@functions@#def-compose}
= & \compose(\compose)(\compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h))(y)(k)(z) \\
& \href{@functions@#def-compose}
= & \compose(\compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h)(y))(k)(z) \\
& \href{@functions@#def-compose}
= & \compose(\compose(\compose(\compose)))(\compose)(f)(g)(x)(h)(y)(k(z)) \\
& \href{@functions@#def-compose}
= & \compose(\compose(\compose))(\compose(f))(g)(x)(h)(y)(k(z)) \\
& \href{@functions@#def-compose}
= & \compose(\compose)(\compose(f)(g))(x)(h)(y)(k(z)) \\
& \href{@functions@#def-compose}
= & \compose(\compose(f)(g)(x))(h)(y)(k(z)) \\
& \href{@functions@#def-compose}
= & \compose(f)(g)(x)(h(y))(k(z)) \\
& \href{@functions@#def-compose}
= & f(g(x))(h(y))(k(z))
\end{eqnarray*}$$
as claimed.
::::::::::::::::::::
::: test :::::::::::
> _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.
:::::: definition ::
[]{#def-compose1on2}
We define $$\composeAonB : (C \rightarrow D) \rightarrow (A \rightarrow B \rightarrow C) \rightarrow A \rightarrow B \rightarrow D$$ by $$\composeAonB = \compose(\compose)(\compose)$$
In Haskell:
> compose1on2 :: (c -> d) -> (a -> b -> c) -> a -> b -> d
> compose1on2 = compose compose compose
::::::::::::::::::::
And $\composeAonB$ behaves like so:
:::::: theorem :::::
[]{#thm-compose1on2}
We have $$\composeAonB(f)(g)(x)(y) = f(g(x)(y)).$$
::: proof ::::::::::
Note that
$$\begin{eqnarray*}
& & \composeAonB(f)(g)(x)(y) \\
& \href{@compose@#def-compose1on2}
= & \compose(\compose)(\compose)(f)(g)(x)(y) \\
& \href{@functions@#def-compose}
= & \compose(\compose(f))(g)(x)(y) \\
& \href{@functions@#def-compose}
= & \compose(f)(g(x))(y) \\
& \href{@functions@#def-compose}
= & f(g(x)(y))
\end{eqnarray*}$$
as claimed.
::::::::::::::::::::
::: test :::::::::::
> _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:
:::::: definition ::
[]{#def-compose1on3}
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:
:::::: theorem :::::
[]{#thm-compose1on3}
We have $$\composeAonC(f)(g)(x)(y)(z) = f(g(x)(y)(z)).$$
::: proof ::::::::::
Note that
$$\begin{eqnarray*}
& & \composeAonC(f)(g)(x)(y)(z) \\
& \href{@compose@#def-compose1on3}
= & \compose(\compose)(\composeAonB)(f)(g)(x)(y)(z) \\
& \href{@functions@#def-compose}
= & \compose(\composeAonB(f))(g)(x)(y)(z) \\
& \href{@functions@#def-compose}
= & \composeAonB(f)(g(x))(y)(z) \\
& \href{@compose@#thm-compose1on2}
= & f(g(x)(y)(z))
\end{eqnarray*}$$
as claimed.
::::::::::::::::::::
::: test :::::::::::
> _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:
:::::: definition ::
[]{#def-compose1on4}
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)$$
In Haskell:
> compose1on4 :: (e -> f) -> (a -> b -> c -> d -> e) -> a -> b -> c -> d -> f
> compose1on4 = compose compose compose1on3
::::::::::::::::::::
And $\composeAonD$ behaves like so:
:::::: theorem :::::
[]{#thm-compose1on4}
We have $$\composeAonD(f)(g)(x)(y)(z)(w) = f(g(x)(y)(z)(w)).$$
::: proof ::::::::::
Note that
$$\begin{eqnarray*}
& & \composeAonD(f)(g)(x)(y)(z)(w) \\
& \href{@compose@#def-compose1on4}
= & \compose(\compose)(\composeAonC)(f)(g)(x)(y)(z)(w) \\
& \href{@functions@#def-compose}
= & \compose(\composeAonC(f))(g)(x)(y)(z)(w) \\
& \href{@functions@#def-compose}
= & \composeAonC(f)(g(x))(y)(z)(w) \\
& \href{@compose@#thm-compose1on3}
= & f(g(x)(y)(z)(w))
\end{eqnarray*}$$
as claimed.
::::::::::::::::::::
::: test :::::::::::
> _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:
:::::: definition ::
[]{#def-compose2on2}
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:
:::::: theorem :::::
[]{#thm-compose2on2}
We have $$\composeBonB(f)(g)(h)(x)(y)(z)(w) = f(g(x)(y))(h(z)(w)).$$
::: proof ::::::::::
Note that
$$\begin{eqnarray*}
& & \composeBonB(f)(g)(h)(x)(y)(z)(w) \\
& \href{@compose@#def-compose2on2}
= & \flipE(\compose(\composeBonA)(\composeBonA))(f)(g)(h)(x)(y)(z)(w) \\
& \href{@flip@#thm-flip5}
= & \compose(\composeBonA)(\composeBonA)(f)(g)(h)(x)(z)(y)(w) \\
& \href{@functions@#def-compose}
= & \composeBonA(\composeBonA(f))(g)(h)(x)(z)(y)(w) \\
& \href{@compose@#thm-compose2on1}
= & \composeBonA(f)(g(x))(h(z))(y)(w) \\
& \href{@compose@#thm-compose2on1}
= & f(g(x)(y))(h(z)(w))
\end{eqnarray*}$$
as claimed.
::::::::::::::::::::
::: test :::::::::::
> _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 () () () () () () ()