{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:05:17Z","timestamp":1779836717764,"version":"3.53.1"},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2008,11,7]],"date-time":"2008-11-07T00:00:00Z","timestamp":1226016000000},"content-version":"unspecified","delay-in-days":4512,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[1996,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The\n                    <jats:italic>Third Homomorphism Theorem<\/jats:italic>\n                    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\n                    <jats:italic>list homomorphism<\/jats:italic>\n                    \u2013 it can be computed according to\n                    <jats:italic>any<\/jats:italic>\n                    parenthesization of the list. We formalize and prove the theorem, and use it to improve an\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    ) sorting algorithm to\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    log\n                    <jats:italic>n<\/jats:italic>\n                    ).\n                  <\/jats:p>","DOI":"10.1017\/s0956796800001908","type":"journal-article","created":{"date-parts":[[2008,11,7]],"date-time":"2008-11-07T11:10:34Z","timestamp":1226056234000},"page":"657-665","source":"Crossref","is-referenced-by-count":50,"title":["Functional Pearls"],"prefix":"10.1017","volume":"6","author":[{"given":"Jeremy","family":"Gibbons","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2008,11,7]]},"reference":[{"key":"S0956796800001908_ref008","unstructured":"Meertens L. G. L. T. (1995) Personal communication."},{"key":"S0956796800001908_ref007","doi-asserted-by":"publisher","DOI":"10.1145\/358886.358892"},{"key":"S0956796800001908_ref004","volume-title":"Computing: The Australian Theory Seminar","author":"Gibbons","year":"1994"},{"key":"S0956796800001908_ref001","first-page":"131","article-title":"Deriving associative operators for language recognition","volume":"43","author":"Barnard","year":"1991","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"S0956796800001908_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(78)80016-2"},{"key":"S0956796800001908_ref005","unstructured":"Gorlatch S. . (1995) Constructing List Homomorphisms. Technical Report MIP-9512, Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t Passau."},{"key":"S0956796800001908_ref002","first-page":"3","volume-title":"Logic of Programming and Calculi of Discrete Design","author":"Bird","year":"1987"},{"key":"S0956796800001908_ref003","first-page":"685","volume-title":"16th Australian Computer Science Conference","author":"Gibbons","year":"1993"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796800001908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:35:25Z","timestamp":1779834925000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796800001908\/type\/journal_article"}},"subtitle":["The Third Homomorphism Theorem"],"short-title":[],"issued":{"date-parts":[[1996,7]]},"references-count":8,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,7]]}},"alternative-id":["S0956796800001908"],"URL":"https:\/\/doi.org\/10.1017\/s0956796800001908","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,7]]}}}