# The Third Homomorphism Theorem

*Jeremy Gibbons*

### 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 describe two practical applications: to fast parallel algorithms for language recognition problems and for downwards accumulations on trees.

Journal

Journal of Functional Programming

Note

Earlier version appeared in B. Jay‚C. editor‚

*Computing: The Australian Theory Seminar*‚ Sydney‚ December 1994‚ 62–6p.9Number

4

Pages

657–665

Volume

6

Year

1996