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

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

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:

• For expression types with many possible constructors, we pay a performance penalty for this representation, when compared to a single "flat expression algebra"
• `Expr`'s `Show` is very cumbersome

### 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:

• No performance penalty when we have many constructors
• Chains of `L1` and `R1` are replaced with a single constructor with a suitable name, so `Show` is slightly more sensible and we can write a term by hand without checking for the order of the constructors

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. • r/haskell