Software Engineering
functions order
Updated Thu, 01 Sep 2022 10:01:33 GMT

What does function composition being associative even mean?


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?




Solution

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).





Comments (5)

  • +0 – 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. — Jul 18, 2022 at 22:41  
  • +0 – @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. — Jul 19, 2022 at 03:19  
  • +0 – 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. — Jul 19, 2022 at 11:09  
  • +0 – @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. — Jul 19, 2022 at 13:47  
  • +6 – @Steve As a programmer, I wouldnt want the first instance of new notation that I encounter to be incorrect and contrary to the established conventions. — Jul 20, 2022 at 17:46  


External Links

External links referenced by this document: