skip to main content
research-article

Conjugate Hylomorphisms -- Or: The Mother of All Structured Recursion Schemes

Published: 14 January 2015 Publication History

Abstract

The past decades have witnessed an extensive study of structured recursion schemes. A general scheme is the hylomorphism, which captures the essence of divide-and-conquer: a problem is broken into sub-problems by a coalgebra; sub-problems are solved recursively; the sub-solutions are combined by an algebra to form a solution. In this paper we develop a simple toolbox for assembling recursive coalgebras, which by definition ensure that their hylo equations have unique solutions, whatever the algebra. Our main tool is the conjugate rule, a generic rule parametrized by an adjunction and a conjugate pair of natural transformations. We show that many basic adjunctions induce useful recursion schemes. In fact, almost every structured recursion scheme seems to arise as an instance of the conjugate rule. Further, we adapt our toolbox to the more expressive setting of parametrically recursive coalgebras, where the original input is also passed to the algebra. The formal development is complemented by a series of worked-out examples in Haskell.

Supplementary Material

MPG File (p527-sidebyside.mpg)

References

[1]
J. Adámek, D. Lücke, and S. Milius, "Recursive coalgebras of finitary functors," RAIRO-Theoretical Informatics and Applications, vol. 41, no. 04, pp. 447--462, 2007.
[2]
R. Backhouse and H. Doornbos, "Datatype-generic termination proofs," English Theory of Comput. Sys., vol. 43, no. 3--4, pp. 362--393, 2008.
[3]
R. Backhouse, M. Bijsterveld, R. van Geldrop, and J. van der Woude, "Categorical fixed point calculus," in Category Theory and Computer Science, ser. LNCS, vol. 953. Springer, Aug. 1995, pp. 159--179.
[4]
R. Bird and O. de Moor, Algebra of Programming. Prentice Hall Europe, 1997.
[5]
R. Bird and R. Paterson, "Generalised folds for nested datatypes," Form. Asp. Comput., vol. 11, no. 2, pp. 200--222, 1999.
[6]
V. Capretta, T. Uustalu, and V. Vene, "Recursive coalgebras from comonads," Inform. Comput., vol. 204, no. 4, pp. 437--468, 2006.
[7]
A. Eppendahl, "Coalgebra-to-algebra morphisms," Electronic Notes in Theoretical Computer Science, vol. 29, no. 0, pp. 42--49, 1999.
[8]
M. M. Fokkinga, "Tupling and mutumorphisms," The Squiggolist, vol. 1, no. 4, pp. 81--82, Jun. 1990.
[9]
P. Freyd, "Algebraically complete categories," in Category Theory, ser. Lect. Notes Math. Springer, 1991, vol. 1488, pp. 95--104.
[10]
T. Hagino, "Category theoretic approach to data types," Ph.D. dissertation, University of Edinburgh, 1987.
[11]
R. Hinze, "Adjoint folds and unfolds--an extended study," Sci. Comput. Program., vol. 78, no. 11, pp. 2108--2159, 2013.
[12]
R. Hinze and N. Wu, "Histo- and dynamorphisms revisited," in Workshop on Generic Program. ACM, 2013, pp. 1--12.
[13]
R. Hinze, N. Wu, and J. Gibbons, "Unifying structured recursion schemes," in ICFP. ACM, 2013, pp. 209--220.
[14]
C. A. R. Hoare, "Notes on data structuring," in Structured Programming, ser. APIC studies in data processing. Academic Press, 1972, pp. 83--174.
[15]
Z. Hu, H. Iwasaki, and M. Takeichi, "Deriving structural hylomorphisms from recursive definitions," in ICFP. ACM, 1996, pp. 73--82.
[16]
J. Kabanov and V. Vene, "Recursion schemes for dynamic programming," in Math. of Prog. Construction, ser. LNCS. Springer, 2006, pp. 235--252.
[17]
D. M. Kan, "Adjoint functors," Trans. Am. Math. Soc., vol. 87, no. 2, pp. 294--329, 1958.
[18]
J. Lambek, "A fixpoint theorem for complete categories," Math. Z., vol. 103, pp. 151--161, 1968.
[19]
S. Mac Lane, Categories for the Working Mathematician, 2nd ed., ser. Graduate Texts in Mathematics. Springer, 1998.
[20]
G. Malcolm, "Algebraic data types and program transformation," Ph.D. dissertation, University of Groningen, 1990.
[21]
----, "Data structures and program transformation," Sci. Comput. Program., vol. 14, no. 2--3, pp. 255--280, 1990.
[22]
L. Meertens, "Paramorphisms," Form. Asp. Comput., vol. 4, pp. 413--424, 1992.
[23]
E. Meijer, M. Fokkinga, and R. Paterson, "Functional programming with bananas, lenses, envelopes and barbed wire," in Functional Programming Languages and Computer Architecture, ser. LNCS, vol. 523. Springer, 1991, pp. 124--144.
[24]
S. Milius, "Completely iterative algebras and completely iterative monads," Inform. Comput., vol. 196, no. 1, pp. 1--41, 2005.
[25]
G. Osius, "Categorical set theory: A characterization of the category of sets," J. Pure Appl. Algebra, vol. 4, no. 1, pp. 79--119, 1974.
[26]
A. Pardo, "Generic accumulations," in IFIP TC2 Working Conference on Generic Program., vol. 24 Kluwer Academic Publishers, Jul. 2002, pp. 49--78.
[27]
P. Taylor, Practical Foundations of Mathematics, ser. Cambridge Studies in Adv. Math. Cambridge University Press, 1999, no. 59.
[28]
T. Uustalu and V. Vene, "Coding recursion à la Mendler," in Workshop on Generic Program., Jul. 2000, pp. 69--85.
[29]
----, "Primitive (co)recursion and course-of-value (co)iteration, categorically," Informatica, Lith. Acad. Sci., vol. 10, no. 1, pp. 5--26, 1999.
[30]
----, "The recursion scheme from the cofree recursive comonad," Electronic Notes in Theoretical Computer Science, vol. 229, no. 5, pp. 135--157, 2011, Math. Structured Functional Program. 2008.
[31]
T. Uustalu, V. Vene, and A. Pardo, "Recursion schemes from comonads," Nordic J. Comput., vol. 8, pp. 366--390, Sep. 2001.
[32]
V. Vene and T. Uustalu, "Functional programming with apomorphisms (corecursion)," Proceedings of the Estonian Academy of Sciences: Physics, Mathematics, vol. 47, no. 3, pp. 147--161, 1998.

Cited By

View all

Index Terms

  1. Conjugate Hylomorphisms -- Or: The Mother of All Structured Recursion Schemes

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 50, Issue 1
    POPL '15
    January 2015
    682 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/2775051
    • Editor:
    • Andy Gill
    Issue’s Table of Contents
    • cover image ACM Conferences
      POPL '15: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
      January 2015
      716 pages
      ISBN:9781450333009
      DOI:10.1145/2676726
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 14 January 2015
    Published in SIGPLAN Volume 50, Issue 1

    Check for updates

    Author Tags

    1. adjunctions
    2. hylomorphisms
    3. recursion schemes

    Qualifiers

    • Research-article

    Funding Sources

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)38
    • Downloads (Last 6 weeks)10
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Tic tac types: a gentle introduction to dependently typed programming (functional pearl)Proceedings of the 4th ACM SIGPLAN International Workshop on Type-Driven Development10.1145/3331554.3342606(40-51)Online publication date: 18-Aug-2019
    • (2018)Steps and TracesCoalgebraic Methods in Computer Science10.1007/978-3-030-00389-0_8(122-143)Online publication date: 20-Sep-2018
    • (2016)Incremental Computing with Abstract Data StructuresFunctional and Logic Programming10.1007/978-3-319-29604-3_14(215-231)Online publication date: 21-Feb-2016
    • (2015)Fusion for FreeMathematics of Program Construction10.1007/978-3-319-19797-5_15(302-322)Online publication date: 9-Jun-2015
    • (2022)Fantastic Morphisms and Where to Find ThemMathematics of Program Construction10.1007/978-3-031-16912-0_9(222-267)Online publication date: 26-Sep-2022
    • (2021)Steps and tracesJournal of Logic and Computation10.1093/logcom/exab05031:6(1482-1525)Online publication date: 23-Aug-2021
    • (2019)Abstracting extensible data types: or, rows by any other nameProceedings of the ACM on Programming Languages10.1145/32903253:POPL(1-28)Online publication date: 2-Jan-2019
    • (2015)How functional programming matteredNational Science Review10.1093/nsr/nwv0422:3(349-370)Online publication date: 13-Jul-2015
    • (2015)Fusion for FreeMathematics of Program Construction10.1007/978-3-319-19797-5_15(302-322)Online publication date: 9-Jun-2015

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media