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:

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