Proving associativity

Question
1

I have this function

def andThen[A,B,C](f: A => B, g: B => C): A => C = {
a => g(f(a))
}

I am trying to prove right association is the same as left association. But i end up with this and they seem different…some help please

//right association
f andThen (g andThen h)
//inline outer andThen
a => (g andThen h)(f(a)) 
//inline inner andThen
a => (b => h(g(b))(f(a)) 
//apply f(a)
a => (f(a) => h(g(f(a))))


// left association
(f andThen g) andThen h
//inline outer andThen
a => h((f andThen g)(a)) 
//inline innner andThen
a => h((b => g(f(b)))(a)) 
//apply a
a => h(a => g(f(a)))
2

Disclaimer, I do not know formal terms.
But, your problem is the way you are applying the function.

So, let’s just focus on that part first.

// If I have a function like
a => a + 1
// And I want to apply it to some value, like:
(a => a + 1)(2)
// I would replace it like this:
2 + 1
// Basically, replacing all the occurrences of the left variable in the right expression.

So, returning to your prove.

// Right association.
f andThen (g andThen h)
// Inline outer andThen
a => (g andThen h)(f(a))
// Inline inner andThen
a => (b => h(g(b))(f(a))
// Apply f(a)
a => h(g(f(a)))

// Left association.
(f andThen g) andThen h
// Inline outer andThen
a => h((f andThen g)(a))
// Inline innner andThen
a => h((b => g(f(b)))(a))
// Apply a
a => h(g(f(a)))

And now you can see both sides are reduced to the same expression.

1 Like