Hinze and Wu begin with the following claim: “Datatype-generic programming (DGP) aims at making your life as a programmer easier by making your programs more general and more robust.” Haskell programmers are convinced of this through a variety of compiler extensions and libraries. However, it is unclear whether these tools are well grounded in theory. This is surprising, as the authors note, since the origins of DGP were firmly grounded in category theory before being re-expressed in type theoretical terms. Since then, researchers have found deeper connections between actual implementations and categorical constructions--in other words, practitioners have remedied what the early theoreticians missed. It is now time to revisit the theory and remake the link to practice; this is what the authors achieve here.
For someone reasonably well versed in category theory, especially as it’s used to model data types, this paper is easy to read. The authors make an effort to speak to readers lacking the necessary background, but in this they fail. While the authors provide the requisite definitions, readers can’t be expected to sufficiently internalize them quickly enough to be able to follow the development. Readers might also notice that the authors use a few sentences almost verbatim in both the abstract and the main text, which is annoying.
The paper is otherwise excellent. Carefully going back and forth between generic Haskell code and category theory, the authors slowly introduce readers to an interesting theoretical framework that nicely explains the current understanding of these generic programs. The elegance is striking. On the other hand, I can’t quite shake the feeling that what is going on here is universal algebra performed one level up.
Anyone serious about DGP should read this paper.