0

Bartosz Milewski, in his book "Category Theory for Programmers" says that:

Composition is associative. If you have three morphisms, f, g, and h, that can be composed (that is, their objects match end-to-end), you don’t need parentheses to compose them. In math notation this is expressed as:

h∘(g∘f) = (h∘g)∘f = h∘g∘f

While trying to understand how to write composable code I want to be able to recognize when my code is NOT composable. Should be simple, right - my functions should comply with the equation h∘(g∘f) = (h∘g)∘f

But when I'm trying to translate it into code I have problem finding functions that are not associative.

Even functions that mutate state seems to have this property.

Example:
Let say I have following functions:

static int a;

void ZeroInc()
{
    a = 0;
    a++;
}

void Inc()
{
    a++;
}

void Zero()
{
    a = 0;
}

void IncInc()
{
    a++;
    a++;
}

I've intentionally written here functions that mutate global state to show that that global state can also be treated as (implicit) function input.
It doesn't matter if I'll call them like this:

ZeroInc();  // a = 1
Inc();      // a = 2

or like this

Zero();     //a = 0
IncInc();   //a = 2

In both cases as a result I have a = 2;

Which means that I can also write just

a = 0;
a++;
a++;

and have the same result.

Can someone show me example of programming function/code that is not associative (and therefore not composable)?
Please show me how it doesn't obey h∘(g∘f) = (h∘g)∘f equation.

2

finding functions that are not associative

You got it wrong. It's not about associativity of functions, but about associativity of function composition. And function composition is always associative....

.... as long as the functions can be composed (otherwise, there's nothing to speak about). The relevant part is

their objects match end-to-end

So take one function operating on strings and another one operating on points. There's no composition at all.....


I guess, you were expecting too much from the cited paragraph.

Answer to a comment

But then, how this relates to binary functions like subtraction or division which match end-to-end, yet everywhere I read, they're not associative?

Sure, they're not, but the article deals with function composition rather with functions themselves. A two-argument function as such is not something composable. You can view it as an one-argument function taking a pair and returning the difference:

f = (a, b) → a - b
g = c → (c, c + 1)
h = (d, e) → d / e

g∘f = (a, b) → (a - b, a - b + 1)
h∘g = c → c / (c + 1)
h∘(g∘f) = (a, b) → (a - b) / (a - b + 1)
  • Thank you. You seem to be right, because I've asked for one parameter function. But then, how this relates to binary functions like subtraction or division which match end-to-end, yet everywhere I read, they're not associative? – SeeR Dec 5 '19 at 12:13
  • @SeeR See my edit. Damn.... the other answer did it already. – maaartinus Dec 6 '19 at 2:56
2

Let's tackle your confusion. You say subtraction is not associative:

a - (b - c) != (a - b) - c

Subtraction maps a pair of numbers to a single number, so the type does not match end-to-end! This is not function composition as described in the question!

Let's consider three functions where they do match and so can be composed:

f(a,b) = (a - b, b)
g(a,b) = (a, a - b)
h(a,b) = (b, a)

Then we have:

(f∘(g∘h))(a,b) = f((g∘h)(a,b)) = f(g(h(a,b))) = f(g(b,a)) = f(b, b -a) = (a, b - a)
((f∘g)∘h)(a,b) = (f∘g)(h(a,b)) = (f∘g)(b,a) = f(g(b,a)) = f(b, b -a) = (a, b -a) 

Note You can also compose functions that don't have same input as output:

f: Int -> String
g: String -> Something

f∘g : Int -> Something

Still, function composition is associative.

  • Thank you. That made it clear - product (T, T) is different type then T. – SeeR Dec 5 '19 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.