More Web Proxy on the site http://driver.im/

research-article

Species and functors and types, oh my!

Author:

Brent A. YorgeyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 45, Issue 11

Pages 147 - 158

https://doi.org/10.1145/2088456.1863542

Published: 30 September 2010 Publication History

Abstract

The theory of combinatorial species, although invented as a purely mathematical formalism to unify much of combinatorics, can also serve as a powerful and expressive language for talking about data types. With potential applications to automatic test generation, generic programming, and language design, the theory deserves to be much better known in the functional programming community. This paper aims to teach the basic theory of combinatorial species using motivation and examples from the world of functional programming. It also introduces the species library, available on Hackage, which is used to illustrate the concepts introduced and can serve as a platform for continued study and research.

Supplementary Material

JPG File (haskell-1700-yorgey.jpg)

Download
7.71 KB

MOV File (haskell-1700-yorgey.mov)

Download
129.26 MB

References

[1]

}}Michael Abbott, Thorsten Altenkirch, and Neil Ghani. Categories of Containers. In Foundations of Software Science and Computation Structures, pages 23--38. 2003.

Digital Library

[2]

}}Michael Abbott, Thorsten Altenkirch, Neil Ghani, and Conor McBride. Derivatives of Containers. In Typed Lambda Calculi and Applications, TLCA, volume 2701 of LNCS. Springer-Verlag, 2003.

Digital Library

[3]

}}Michael Abbott, Thorsten Altenkirch, Neil Ghani, and Conor McBride. Constructing Polymorphic Programs with Quotient Types. In 7th International Conference on Mathematics of Program Construction (MPC 2004), volume 3125 of LNCS. Springer-Verlag, 2004.

[4]

}}F. Bergeron, G. Labelle, and P. Leroux. Combinatorial species and tree-like structures. Number 67 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1998.

[5]

}}Jean-Philippe Bernardy, Patrik Jansson, and Koen Claessen. Testing polymorphic properties. In ESOP 2010: Proceedings of the 19th European Symposium on Programming, pages 125--144, London, UK, 2010. Springer-Verlag.

Digital Library

[6]

}}Bird and Meertens. Nested datatypes. In MPC: 4th International Conference on Mathematics of Program Construction. LNCS, Springer-Verlag, 1998.

Digital Library

[7]

}}Benjamin Canou and Alexis Darrasse. Fast and sound random generation for automated testing and benchmarking in objective Caml. In ML '09: Proceedings of the 2009 ACM SIGPLAN workshop on ML, pages 61--70, New York, NY, USA, 2009. ACM.

Digital Library

[8]

}}Jacques Carette and Gordon Uszkay. Species: making analytic functors practical for functional programming. Available at http://www.cas.mcmaster.ca/~carette/species/, 2008.

[9]

}}Koen Claessen and John Hughes. QuickCheck: a lightweight tool for random testing of Haskell programs. In ICFP '00: Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, pages 268--279, New York, NY, USA, 2000. ACM.

Digital Library

[10]

}}Duncan Coutts, Isaac Potoczny-Jones, and Don Stewart. Haskell: batteries included. In Haskell '08: Proceedings of the first ACM SIGPLAN symposium on Haskell, pages 125--126, New York, NY, USA, 2008. ACM.

Digital Library

[11]

}}Jonas Almström Duregård. AGATA: Random generation of test data. Master's thesis, Chalmers University of Technology, December 2009.

[12]

}}P. Flajolet, B. Salvy, and P. Zimmermann. Lambda-upsilon-omega: The 1989 cookbook. Technical Report 1073, Institut National de Recherche en Informatique et en Automatique, August 1989. 116 pages.

[13]

}}Philippe Flajolet and Bruno Salvy. Computer algebra libraries for combinatorial structures. Journal of Symbolic Computation, 20(5-6):653--671, 1995.

Digital Library

[14]

}}Gérard Huet. Functional pearl: The zipper. J. Functional Programming, 7:7--5, 1997.

Digital Library

[15]

}}C. Barry Jay and J. Robin B. Cockett. Shapely types and shape polymorphism. In ESOP '94: Proceedings of the 5th European Symposium on Programming, pages 302--316, London, UK, 1994. Springer-Verlag.

Digital Library

[16]

}}André Joyal. Une théorie combinatoire des Séries formelles. Advances in Mathematics, 42(1):1--82, 1981.

[17]

}}Conor McBride. The Derivative of a Regular Type is its Type of One-Hole Contexts. Available at http://www.cs.nott.ac.uk/~ctm/diff.ps.gz, 2001.

[18]

}}Conor McBride. Clowns to the left of me, jokers to the right (pearl): dissecting data structures. In Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 287--295, San Francisco, California, USA, 2008. ACM.

Digital Library

[19]

}}M. Douglas McIlroy. Power series, power serious. Journal of Functional Programming, 9(03):325--337, 1999.

Digital Library

[20]

}}Peter Morris, Thorsten Altenkirch, and Conor Mcbride. Exploring the regular tree types. 2004.

[21]

}}Dan Piponi. A small combinatorial library, November 2007. http://blog.sigfpe.com/2007/11/small-combinatorial-library.html.

[22]

}}Colin Runciman, Matthew Naylor, and Fredrik Lindblad. Smallcheck and lazy smallcheck: automatic exhaustive testing for small values. In Haskell '08: Proceedings of the first ACM SIGPLAN symposium on Haskell, pages 37--48, New York, NY, USA, 2008. ACM.

Digital Library

[23]

}}Herbert S. Wilf. Generatingfunctionology. Academic Press, 1990.

Digital Library

Cited By

Danielsson N(2012)Bag Equivalence via a Proof-Relevant Membership RelationInteractive Theorem Proving10.1007/978-3-642-32347-8_11(149-165)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32347-8_11
Duregård JJansson PWang M(2012)FeatACM SIGPLAN Notices10.1145/2430532.236451547:12(61-72)Online publication date: 13-Sep-2012
https://dl.acm.org/doi/10.1145/2430532.2364515
Duregård JJansson PWang MVoigtländer J(2012)FeatProceedings of the 2012 Haskell Symposium10.1145/2364506.2364515(61-72)Online publication date: 13-Sep-2012
https://dl.acm.org/doi/10.1145/2364506.2364515

Index Terms

Species and functors and types, oh my!
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Data types and structures
      2. Language types
        Functional languages

Recommendations

Species and functors and types, oh my!
Haskell '10: Proceedings of the third ACM Haskell symposium on Haskell

The theory of combinatorial species, although invented as a purely mathematical formalism to unify much of combinatorics, can also serve as a powerful and expressive language for talking about data types. With potential applications to automatic test ...
Multi-species comparative genomics: synteny and genome rearrangements
Shared subtypes: subtyping recursive parametrized algebraic data types
Haskell '08: Proceedings of the first ACM SIGPLAN symposium on Haskell

A newtype declaration in Haskell introduces a new type renaming an existing type. The two types are viewed by the programmer as semantically different, but share the same runtime representation. When operations on the two semantic views coincide, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 45, Issue 11

HASKELL '10

November 2010

156 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2088456

Issue’s Table of Contents

Haskell '10: Proceedings of the third ACM Haskell symposium on Haskell
September 2010
166 pages
ISBN:9781450302524
DOI:10.1145/1863523
General Chair:
Jeremy Gibbons
University of Oxford, UK

Copyright © 2010 ACM.

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 ACM 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: 30 September 2010

Published in SIGPLAN Volume 45, Issue 11

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
470
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Danielsson N(2012)Bag Equivalence via a Proof-Relevant Membership RelationInteractive Theorem Proving10.1007/978-3-642-32347-8_11(149-165)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32347-8_11
Duregård JJansson PWang M(2012)FeatACM SIGPLAN Notices10.1145/2430532.236451547:12(61-72)Online publication date: 13-Sep-2012
https://dl.acm.org/doi/10.1145/2430532.2364515
Duregård JJansson PWang MVoigtländer J(2012)FeatProceedings of the 2012 Haskell Symposium10.1145/2364506.2364515(61-72)Online publication date: 13-Sep-2012
https://dl.acm.org/doi/10.1145/2364506.2364515

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents