Yufei Cai
AlumniYufei Cai gives an informal talk about the ongoing first-class functors project at PPS Lab, University Paris Diderot.

Abstract

Traversing an algebraic datatype by hand requires boilerplate code duplicating the structure of the datatype. Many datatype-generic programming techniques rewrite a regular datatype so that some traversal patterns can be refactored into a regular functor. This functor is dominant: The traversals it supports are far easier to write than the traversals it does not.

We address the tyranny of the dominant functor by making regular functors first-class: They can be defined independently of data types and can interoperate with all data types that correspond to applications of that functor. By having an open-ended set of functors for each datatype, known generic programming techniques based on functors can now be applied for each of these functors. We avoid boilerplate code in the implementation of these functors by generating them from their type constructors.

To demonstrate feasibility, we prototyped first-class regular functors in a Scala macro library Creg. A challenging technical issue arises due to our iso-recursive encoding of datatypes: Since different functors may correspond to different recursive decompositions of a datatype, the interoperability of these functors requires a “deep” application of the respective roll/unroll isomorphisms. We suppress the problem via a coercion macro based on Amadio and Cardelli’s subtyping algorithm for equirecursive types.

We validate our approach through a set of case studies, demonstrating we can encode different datatype-generic techniques from the literature and have them interoperate.