Nicer Data Types a la Carte with DefaultSignatures 2019.10.02

Back in 2008, Swierstra's Functional Pearl Data Types a la Carte showed how to construct the following data structure:

data Expr = Val Int | Add Expr Expr

from simple and re-usable individual components:

newtype Val e = Val Int deriving Functor
data    Add e = Add e e deriving Functor

type Expr = Fix (Val :+: Add)

(Fix is available in the recursion-schemes package and :+: is available from GHC.Generics)

The Good

This construction allows to write clean and re-usable modular code. For example we can implement evaluation of expressions like this:

class Functor f => Eval f where
    evalAlgebra :: f Int -> Int

eval (Fix expr) = evalAlgebra (fmap eval expr)

instance (Eval f, Eval g) => Eval (f :+: g) where
    evalAlgebra (L1 x) = evalAlgebra x
    evalAlgebra (R1 y) = evalAlgebra y

instance Eval Val where
    evalAlgebra (Val x) = x

instance Eval Add where
    evalAlgebra (Add x y) = x + y

The beautiful part, which makes this a functional pearl, is that the Eval instances of Val and Add are usable not just for the Expr type defined above, but also for any other expression language which re-uses them, such as:

type Expr2 = Fix (Val :+: Add :+: Mul :+: Pow :+: Etc)

The Ugly

How would we represent an expression, such as 1 + 2 in the type defined above?

The simple way to do it is Fix (R1 (Fix (L1 (Val 1)) `Add` Fix (L1 (Val 2)))).

The usages of Fix, R1 and L1 are cumbersome, so to make things easier Swiestra showed how to write the expression as val 1 `add` val 2 using an additional type-class and lifting functions per constructor. This makes writing terms convinient, but a few problems remain unsolved:

Bringing the benefits of Data Types a la Carte to simpler representations

A few years after the paper, in 2011, DefaultSignatures were added in GHC 7.2. These enable a more direct construction of Expr:

data Expr a = EVal (Val a) | EAdd (Add a)
    deriving (Generic1, Functor, Eval)

Of note here is the derivation of Eval (using DeriveAnyClass). Making Eval derivable is a simple matter of adding default method implementations in the Eval class along with two trivial instances for types from GHC.Generics:

class Functor f => Eval f where
    evalAlgebra :: f Int -> Int
    default evalAlgebra :: (Generic1 f, Eval (Rep1 f)) => f Int -> Int
    evalAlgebra = evalAlgebra . from1

deriving newtype instance Eval f => Eval (M1 i c f)
deriving newtype instance Eval f => Eval (Rec1 f)

This gives us a few benefits:

The Bad

While Data Types a la Carte allows us to re-use individual components such as Val and Add in expression types, those are limited to be simple recursive types.

Haskell's AST

In practice, programming language ASTs tend to consist of multiple mutually-recursive types, and Data Types a la Carte's approach can't help us express those. I'll expand on how to extend its approach for more complicated ASTs in a future post.