DEV Community

loading...
Cover image for Composition of Function Composition - (.).(.)

Composition of Function Composition - (.).(.)

ingun37 profile image Ingun 전인건 Updated on ・3 min read

You must be familiar with function composition.

f:BCg:ABh=fgh:AC f : B \rightarrow C \newline g : A \rightarrow B \newline h = f \circ g \newline h: A \rightarrow C

Well, function composition itself is a function right? What do you think will happen when you compose compositions?

()()=? (\circ) \circ (\circ) = ?

It becomes another composition operator that can compose an unary function and a binary function. That is to say,

f:CDg:A×BC f: C \rightarrow D \newline g: A \times B \rightarrow C

Now let hh be

h=f(()())g h = f \left( (\circ) \circ (\circ) \right) g

Then hh is

h:A×BDh(a,b)=f(g(a,b)) h : A \times B \rightarrow D \newline h(a,b) = f(g(a,b))

We can go one step further and compose three compositions.

f:DEg:A×B×CDh:A×B×CEh=f(()()())gh(a,b,c)=f(g(a,b,c)) f : D \rightarrow E \newline g : A \times B \times C \rightarrow D \newline h : A \times B \times C \rightarrow E \newline h = f \left( (\circ) \circ (\circ) \circ (\circ) \right) g \newline h(a,b,c) = f(g(a,b,c))

It becomes a composition operator that can compose an unary function and a ternary function. In other words, the degree of the domain increases by 1 everytime we compose another composition.

You may be wondering how it is possible. You can try direct proof first to see the mechanism although it won’t tell you much about the idea behind it. I’ll put the brief, outline proof just to make the point of how unhelpful it is.

Signature of function composition is

:(βγ)×(αβ)(αγ) \circ: (\beta \rightarrow \gamma) \times (\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma)

Both parameters are also composition functions therefore the signatures of α,β,γ\alpha, \beta, \gamma are

α:yzβ:(xy)(xz)γ:(a(xy))(a(xz)) \alpha : y \rightarrow z \newline \beta : (x \rightarrow y) \rightarrow (x \rightarrow z) \newline \gamma : (a \rightarrow (x \rightarrow y)) \rightarrow (a \rightarrow (x \rightarrow z))

Therefore the signature of the outcome is

αγ=(yz)(axy)(axz) \alpha \rightarrow \gamma = (y \rightarrow z) \rightarrow (a \rightarrow x \rightarrow y) \rightarrow (a \rightarrow x \rightarrow z)

Which is the signature of unary-binary-composition function.

As you can see it doesn’t tell you why. It’s like saying 2x2x is the slope of the tangent line of x2x^2 without mentioning derivative.

If you know Hom functor then much better explanation is possible.

You can consider a function composition as a hom-functor in category theory’s perspective. To present function composition as hom-functor:

hom(x,):(yz)(yxzx) \circ_{hom(x,-)} : (y \rightarrow z) \rightarrow (y^x \rightarrow z^x)

Alt Text

If you are not familiar with xyx^y notation, you can just think of it as a function yxy \rightarrow x

And here’s the composition of two function compositions

hom(x,)hom(a,):(yz)(yxazxa) \circ_{hom(x,-)} \circ \circ_{hom(a,-)} : (y \rightarrow z) \rightarrow (y^{xa} \rightarrow z^{xa})

Alt Text

You can construct h:x×azh: x\times a \rightarrow z universally with f:yzf: y\rightarrow z and g:x×ayg: x\times a \rightarrow y

Here’s an application in programming. Say you are making a function that calculates a vector’s magnitude. It’s always encouraged to use squared magnitude instead of actual magnitude unless it’s absolutely necessary for performance reasons therefore you have to support both functionalities. You can implement squaredMagnitude first and then implement magnitude by composing sqrt and squaredMagnitude using the discussed method.

(.*) :: (c -> d) -> (a -> b -> c) -> (a -> b -> d)
(.*) = (.) . (.)

squaredMagnitude :: Double -> Double -> Double
squaredMagnitude x y = x^2 + y^2

magnitude = sqrt .* squaredMagnitude

main :: IO ()
main = do
  print $ squaredMagnitude 3 4
  print $ magnitude 3 4

It outputs

25.0
5.0

Discussion (0)

pic
Editor guide