21

When we have a math problem such as 3 + 5 + 2, we say that it is associative. We can choose which step to pick first: 3 + (5 + 2); we know that brackets affect the order in which the operations are performed.

I've learned that function composition is a binary operation and it is also associative. They say, function composition is the scenario where an output of one function is used as an input of another; like method chaining.

The problem is that I am struggling to imagine how to combine two functions together. I've seen online a function called combine that takes two functions as arguments and then returns the third function that just calls these two functions one after another; but that doesn't affect anything at all. It is just an alias, like if it were a + b + c and became a + d, where d = b + c. It doesn't affect anything really.

I am not sure what should be even affected in here; obviously it's not the order in which the functions are executed, since the execution itself is not a binary operation. So what is the binary operation in function composition then? What's the difference between a scenario when we compose two functions together and when we don't?

Improve this question
10
  • 2
    Technically, the brackets affect the binding of operators to operands, effectively adjusting their precedence. That then sometimes influences an ordering of operations, but there are examples where the brackets only partially dictate the order of operations, such as (3+4)*(5+6), where the order of the two additions there remains unspecified by mathematics. Commented Jul 18, 2022 at 14:26
  • 1
    "I am struggling to imagine how to combine two functions together" And a definition of "function composition" for binary functions is what? Commented Jul 19, 2022 at 7:22
  • 1
    People don't like the scary monad word but it's an excellent, practical example of assiociative function composition: map(map(array, f), g) should be equal to map(array, g ∘ f) where one may be more readable and the other more performant. You can choose the more readable path while your compiler is free to rewrite your code into something equivalent but faster. Commented Jul 19, 2022 at 12:10
  • 1
    "What's the difference between a scenario when we compose two functions together and when we don't?" One could ask what the difference between 5+2 and 7 is. The two expressions represent the same value, but one of them gives a number directly while the other gives it as a composition of two other numbers. Function composition is no different. Commented Jul 20, 2022 at 17:53
  • 1
    @Schmid that's a good example, but it doesn't actually involve any monad (map is simply a functor operation). Commented Jul 21, 2022 at 13:16

4 Answers 4

Reset to default
26

I think "functional composition" tends to be a bit confusing.

By "compose" what we mean is piping the output of one function to the input of another.

Most modern programming languages have some facility for evaluating expressions, and we are accustomed to seeing composition occur in the form of Sqrt(Add(2, 2)), where the output of 'Add' forms the input for 'Sqrt'.

What's notable about this familiar form of composition is that the operands which form the ultimate input (in this case, a pair of '2's) must also be specified at the same time as the composition. You can use variables in place of literals, but you still have to provide something for the operands, as part of specifying the composition.

However, in functional languages, the composition operator allows these two functions to be composed without specifying anything for the operands.

The evaluation of AddAndSqrt = (Add ∘ Sqrt) gets the function pointers for both 'Add' and 'Sqrt' (so that these functions are not called in this expression, but instead their addresses are evaluated as function pointers, and then these are provided as operands to the composition operator), and returns a new function pointer, which takes two operands (effectively, the inputs to the 'Add' stage), and when called like so AddAndSqrt(2, 2), outputs the same result as would Sqrt(Add(2, 2)).

Behind the scenes, the output of the 'Add' stage is arranged so as to be piped to the input of the 'Sqrt' stage. That is what the composition operator does.

Now, composition is an associative operator simply because in the expression C(B(A(2, 2))) it doesn't matter whether you pipe A to B (yielding AB) then pipe AB to C (yielding ABC), or pipe B to C (yielding BC) then pipe A to BC (yielding ABC).

Or to put it another way, it doesn't matter if you write:

 Result1 = B(A(2, 2)) Result2 = C(Result1) OR Result1 = A(2, 2) Result2 = C(B(Result1))

In both cases, the chain of calls you end up with is equivalent to C(B(A(2, 2))).

That's all it means for the composition operator to be associative.

All "operators" in mathematics have a set of "properties" - like associativity - that concern their behaviour under algebraic rearrangement. That is, concerning whether different kinds of rearrangement within an expression cause the result to change, or whether the result stays the same despite the rearrangement.

Has that answered the question?

Edit: a number of commentators have pointed out that the standard convention when using the function composition operator ∘ is that the first-applied argument goes on the right. So that the equivalent of C(B(A(x,y))) would be (C ∘ B ∘ A)(x, y) in typical functional languages, and certainly so in general mathematics.

However I think that many programmers would readily prefer the idea that the sequencing of operations proceeds in English order left-to-right, so I'm going to leave the main body of the answer as it is.

I was also pleased to find that in F#, composition can be done left to right in accordance with my preference, although using a different symbol for the composition operator (>>): https://fsharpforfunandprofit.com/posts/function-composition/

So that C(B(A(x,y))) would become (A >> B >> C)(x, y).

Improve this answer
18
  • 10
    There are plenty of interesting points in this answer. As a side remark, an important notation issue: (f o g)(x) means f(g(x)). So AddAndSqrt (i.e. taking the output of add as input of sqrt, should be noted Sqrt o Add. Commented Jul 18, 2022 at 22:41
  • 16
    @Steve I think you're just going to end up confusing anybody who's new to this by not using o correctly. And anyway, preferences not withstanding,AddAndSqrt(...) is still Sqrt(Add(...)) and not Add(Sqrt(...)), so not always left to right. Commented Jul 19, 2022 at 3:19
  • 17
    It's not a "convention" that (f ∘ g)(x) == f(g(x)); it's the definition. If you think that ordering is confusing, fine, but don't redefine a commonly used symbol just because you disagree with its definition; pick a different symbol. Commented Jul 19, 2022 at 11:09
  • 12
    @Steve Given that you agree that the definition is completely arbitrary, I don't understand your reluctance to follow established conventions. Someone who hasn't run into the concept and symbol before will have to learn what it means anyhow, but your choice confuses everyone else. And worse: Anyone who learns the concepts here will then be very confused when they see the symbol anywhere else. Commented Jul 19, 2022 at 13:47
  • 6
    @Steve As a programmer, I wouldn’t want the first instance of new notation that I encounter to be incorrect and contrary to the established conventions. Commented Jul 20, 2022 at 17:46
20

Function composition doesn't operate on the same arguments as the functions do. If operates on the functions as arguments. And since you can designate functions by symbols and invent a (meta-)functor that operates on functions, this meta-construct satisfies the formal definition of associativity: f ∘ (g ∘ h) == (f ∘ g) ∘ h.

The fact that you find this obvious, or can't even imagine how it could be otherwise doesn't change this. After all, addition is commutative and most people can't imagine how that could possibly be different either. You have to advance quite far in mathematics (to Hamiltonian quaternions, say) until it's not commutative any more.

Improve this answer
8
  • When you say "one can invent a (meta-)functor that operates on functions", could you give an example please? I am not sure what are you talking about. But overall it sounds pretty convincing. Commented Jul 18, 2022 at 13:01
  • 1
    @pro100tom In Java: Predicate<String> startsWithA = (text) -> text.startsWith("A"); Predicate<String> endsWithX = (text) -> text.endsWith("x"); Predicate<String> startsWithAAndEndsWithX = (text) -> startsWithA.test(text) && endsWithX.test(text); Commented Jul 18, 2022 at 13:04
  • 1
    @pro100tom: Use the above example as a guideline where you have 3 checks instead of 2 (starts with A, ends with X, contains a Z), and realize that A && (X && Z) == (A && X) && Z Commented Jul 18, 2022 at 13:17
  • 1
    @SirHawk: That's not composition of predicates though, the predicates are composed not with each other but with an intersection operation, and you're looking at associativity of intersection, not of function composition. Commented Jul 18, 2022 at 22:09
  • 1
    Side note to your quaternion example: addition of quaternions is commutative, multiplication isn't. For simple examples of non-commutative groups, I would start here: en.wikipedia.org/wiki/Non-abelian_group Commented Jul 19, 2022 at 5:51
10

Other answers have explained this well in programming terms. But I think it's possible using only familiar mathematical notation, too. Here goes…

Suppose you have three functions: f, g, and h, so that:
   f(x) = (some function of x)
   g(x) = (some other function of x)
   h(x) = (yet another function of x)

(Of course, those are three different ‘x’s!)

And suppose that you want to apply them in turn, i.e. to calculate
   f(g(h(x)))
for some x. Or in other words, you want to compose the three functions.

To simplify this, let's define a couple of new functions, which I'm going to give the stunningly original names fg and gh:
   let fg(x) = f(g(x))
and
   let gh(x) = g(h(x))

So we can use them to express our desired result in three different ways:
   fg(h(x))
   f(gh(x))
   f(g(h(x)))

All three of those give the same result (for all values of x). That's because it doesn't matter whether we compose f and g, and then compose the result with h, or we compose f with the result of composing g and h; the end result is the same.

I hope you can see the parallel with addition being associative. The above is saying that function composition is associative.

(‘Real’ mathematics would write this in a different notation, using the ring operator ‘∘’ to represent function composition:
   (f ∘ g) ∘ h = f ∘ (g ∘ h)
That's simpler and makes the parallel clearer, but of course it's more abstract without the ‘x’s, and harder to follow if you're not used to it. But it means exactly the same.)

Improve this answer
6
  • This cracks me up! Only a mathematician could possibly think that assigning these functions the arbitrary names f, g, and h, only to then apply them in counter-alphabetical order h, g, f, was a reasonable naming convention! It's actually a brilliant answer for how it illustrates how mathematicians just don't get it - it's like numbering the paragraphs of your instruction booklet Z to A! Commented Jul 19, 2022 at 5:46
  • 1
    I think you mean gh(x) = g(h(x)) not h(g(x)) Commented Jul 19, 2022 at 19:15
  • @Steve f,g,h don't necessarily imply any order in composition. Maybe postfix notation like x h g f makes more sense (it goes left-to-right, like a unix pipe) Commented Jul 19, 2022 at 21:24
  • @user253751 Well done for spotting the, er, deliberate mistake… %-) Now fixed, ta! Commented Jul 19, 2022 at 21:46
  • 2
    @qwr, it's precisely my point. Programmers are concerned about rhyme and reason in naming. The naming here is arbitrary but a sequencing is specified. A programmer would most likely choose a naming scheme that accorded with the order of application. When you write a book, the numbering of the chapters is not necessarily meaningful, but you do number things in reading order - no author designates the first chapter of the book Chapter Z, and then progresses through to finish at Chapter A. I know from experience that mathematicians have a blind spot in this area of communication. Commented Jul 19, 2022 at 23:39
8

I'll go straight to the maths where the previous answers didn't dare...

Saying "function composition is associative" means that you have an operator (which we call "function composition"). A mathematical operator in general maps one or more elements from some domain(s) onto elements in another domain. In our case, all domains are the function space.

So the composition operator "∘" maps from two functions to a new function. This mapping is defined thus:

  • Given f, g are functions
  • then we define f ∘ g to be a function as well (to be precise: the operator ∘ maps any two functions onto a function; or in software engineering terms, it creates a function which refers to two other functions)
  • and we define (f ∘ g)(x) := f(g(x))
  • (implicitely and obviously, the domains of f and g must match to be compatible with each other).

If we now have three functions f, g, h, it makes sense to ask about associvity; i.e. f ∘ (g ∘ h) =? (f ∘ g) ∘ h. You can see this easily by substituting the definition:

  • (f ∘ (g ∘ h))(x) = f((g ∘ h)(x)) = f(g(h(x)))
  • ((f ∘ g) ∘ h)(x) = (f ∘ g)(h(x)) = f(g(h(x)))
  • q.e.d.
Improve this answer
6
  • 1
    And if all the functions have the same domain and codomain, the algebraic structure formed by these function compositions over functions is the transformation monoid. Commented Jul 19, 2022 at 21:22
  • Right! We can prove associativity of function composition ... under very mild hypotheses... not only for "functions mapping sets to sets", but, also, somewhat fancier things... though, indeed, this argument seems to use the fact that functions have inputs, etc. Commented Jul 19, 2022 at 21:31
  • @paulgarrett, sure, after all we're on softwareengineering.SE, not maths.SE, so I wanted to keep it short and sweet. Commented Jul 20, 2022 at 9:41
  • Just a side note on notation, the usual symbol for function composition is a raised circle ∘ (U+2218), not a lowercase o. (Depending on your font and/or vision, an o maybe easier to read than a ∘.) Commented Jul 21, 2022 at 16:55
  • Thanks @chepner! I tried $\circ$ when I first wrote the answer, but it seems that "latex" math-style is not activated on SWE.SE so I bailed out with the "o" :) . Going right to the proper unicode char is best of course and I have replaced it. Commented Jul 22, 2022 at 7:28

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.