Sean Seefried

Title: Solving the expression problem in Haskell

Abstract:

In 1998 Philip Wadler coined the term "the expression problem" to describe the difficulty, in many languages, of simultaneously adding new variants to a data structure and new methods that operate on that data structure without modifying existing code.  In object-oriented languages it is easy to add to variants to a data structure via sub-classing. But adding new methods requires the modification of the base class. In functional languages it is easy to add new methods (functions) but adding a new variant requires modification of the data type declaration.

However, a number of solutions have been proposed. Two notable languages which solve this problem are Scala and Ocaml (via polymorphic variants).  In this talk I shall present a solution in Haskell. It requires a number of experimental extensions such as multi-parameter type classes, recursive dictionaries, and a relaxed form of overlap checking.  The result can be viewed in two ways. First, as an idiomatic method for programmers to write extensible data types. Second, as the target encoding of a translation from Haskell augmented with syntactic sugar for extensible data types.