Scala for Generic Programmers

Datatype-generic programming involves parametrization of programs by the shape of data, in the form of type constructors such as \"list of\". Most approaches to datatype-generic programming are developed in pure functional programming languages such as Haskell. We argue that the functional object-oriented language Scala is in many ways a better choice. Not only does Scala provide equivalents of all the necessary functional programming features (such as parametric polymorphism, higher-order functions, higher-kinded type operations, and type- and constructor-classes), but it also provides the most useful features of object-oriented languages (such as subtyping, overriding, traditional single inheritance, and multiple inheritance in the form of traits). Common Haskell techniques for datatype-generic programming can be conveniently replicated in Scala, whereas the extra expressivity provides some important additional benefits in terms of extensibility and reuse. We illustrate this by comparing two simple approaches in Haskell, pointing out their limitations and showing how equivalent approaches in Scala address some of these limitations. Finally, we present three case studies on how to implement in Scala real datatype-generic programming approaches from the literature: Hinze's \"Generics for the Masses\", Laemmel and Peyton Jones's \"Scrap your Boilerplate with Class\", and Gibbons's \"Origami Programming\"