Functional Pearls
- 1 July 1996
- journal article
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 6 (4) , 657-665
- https://doi.org/10.1017/s0956796800001908
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).Keywords
This publication has 2 references indexed in Scilit:
- On folk theoremsCommunications of the ACM, 1980
- On program synthesis knowledgeArtificial Intelligence, 1978