ICFP 2018 (series) / Research Papers /
What's the Difference? A Functional Pearl on Subtracting Bijections
It is a straightforward exercise to write a program to “add” two bijections—resulting in a bijection between two sum types, which runs the first bijection on elements from the left summand and the second bijection on the right. It is much less obvious how to “subtract” one bijection from another. This problem has been studied in the context of combinatorics, with several computational principles known for producing the ``difference'' of two bijections. We consider the problem from a computational and algebraic perspective, showing how to construct such bijections at a high level, avoiding pointwise reasoning or being forced to construct the forward and backward directions separately—without sacrificing performance.
Wed 26 Sep Times are displayed in time zone: Guadalajara, Mexico City, Monterrey change
Wed 26 Sep
Times are displayed in time zone: Guadalajara, Mexico City, Monterrey change
10:30 - 12:00: SemanticsResearch Papers at Stifel Theatre Chair(s): Sam LindleyUniversity of Edinburgh, UK | |||
10:30 - 10:52 Talk | Partially-Static Data as Free Extension of Algebras Research Papers Jeremy YallopUniversity of Cambridge, UK, Tamara von GlehnUniversity of Cambridge, Ohad KammarUniversity of Oxford Link to publication DOI Pre-print | ||
10:52 - 11:15 Talk | Relational Algebra by Way of AdjunctionsDistinguished Paper Research Papers Jeremy GibbonsDepartment of Computer Science, University of Oxford, Fritz HengleinDepartment of Computer Science, University of Copenhagen (DIKU), Ralf HinzeRadboud University Nijmegen, Nicolas WuUniversity of Bristol, UK DOI | ||
11:15 - 11:37 Talk | Strict and Lazy Semantics for Effects: Layering Monads and Comonads Research Papers DOI | ||
11:37 - 12:00 Talk | What's the Difference? A Functional Pearl on Subtracting Bijections Research Papers DOI |