Abstract:
The Third Homomorphism Theorem is a folk theorem of the constructive algorithmics
community. It states that a function on lists that can be computed both from left to right
and from right to left is necessarily a list homomorphism – it can be computed according
to any parenthesization of the list.
We formalize and prove the theorem, and use it to improve an O(n2) sorting algorithm
to O(n log n).