The unreasonable effectiveness of polymorphic records

Record types are an important part of typed functional programming languages. Separating data from behaviour creates the need for a convenient representation of key-value pairs. Most of the time, such records are monomorphic: each field has a specific type. Using record types this way (forgetting Haskell record idiosyncrasies for a minute) should be familiar to most of you. Haskell is also well known for its pervasive use of parametric polymorphism; as always, digging at the intersection of two interesting ideas is time well spent. Let’s have a look at a few patterns combining records and polymorphism. It should be fun!

Step 0: Monomorphic Records

Most records are monorphic. Here, the record type Account has kind Type: it is a regular type, with no type parameters.

data Account = Account {
  accountId :: Int,
  fullName :: Text
}
deriving stock (Eq, Show, Generic)
deriving anyclass (FromJSON, ToJSON)

The Haskell ecosystem provides us with quite a lot of tooling: here we derive Eq and Show instances, as well as Generic. Generic acts as an extension point, allowing other libraries to gain access to structural information and provide more tooling for free (conditions may apply). In this case, Generic allows us to derive JSON codecs. aeson’s FromJSON and ToJSON provide conversion from/to JSON objects shaped like our record.

This kind of tooling is not specific to Haskell, and is becoming commonplace even in more mainstream languages like Java.

Let’s have a look at more sophisticated use cases, and see how far we can go.

Step 1: The Humble Wrapper

Some records are intended as metadata wrappers around other data. Let’s consider pagination: instead of returning a list of all Account values we want to return only a limited number of them, with pointers to more accounts. One naive way to do that would be the following:

data PaginatedAccounts = PaginatedAccounts {
  pages :: Int,
  previous :: Maybe Int,
  next :: Maybe Int,
  items :: [Account]
}
deriving stock (Eq, Show, Generic)
deriving anyclass (FromJSON, ToJSON)

This is unsatisfying: pagination is a cross-cutting concern that appears in a lot of places. Creating a new Paginated- variant for each type would require a lot of boilerplate code and would make room for inconsistencies. So we definitely want to be describe pagination once, and then use it across our application.

In that case, making the items field polymorphic will do just what we want. We can still derive typeclasses like Eq, Show, as well as, for instance, aeson classes like FromJSON and ToJSON. The compiler will make sure that, when using these instances, a is implementing them as well.

data Paginated a = Paginated {
  pages :: Int,
  previous :: Maybe Int,
  next :: Maybe Int,
  items :: [a]
}
deriving stock (Eq, Show, Generic)
deriving anyclass (FromJSON, ToJSON)

Note that a is the type of one paginated item, not of the list of items.

Supercharging extensions

Deriving Eq, Show or aeson instances feel natural (after all, many other languages provide similar mechanisms). But this is Haskell, and we shouldn’t be afraid to dream a little bigger. GHC can derive Functor, Foldable, and Traversable (with the help of DeriveTraversable, which is enabled by default in the GHC2021 extension set) for us. With them, the humble wrapper can be used in many more contexts.

  …
  deriving stock (…, Functor, Foldable, Traversable)

The humble wrapper makes no assumptions about its contents. It lets you derive typeclass instances with no hand-holding, happily threading dependencies for you. It is now also more versatile, thanks to the Traversable instance and its friends. It lets you work with intermediate structures inferred on the go, without the need to plan them in advance.

For cross-cutting concerns that are highly generic, simple polymorphic records like this are a great fit. The Paginated record is defined separately from the items it will hold, and typeclasses take care of encoding dependencies. Sadly, not all problems look like this. In some cases, there is more coupling between the record itself and the moving parts it contains.

Step 1-bis

Let’s look at a different example. Here we want to model a database record, before and after insertion in a database. Before insertion, the primary key does not exist yet. It is generated by the database server when creating the database row.

data DatabaseRecord pk =
  DatabaseRecord {
    recordId :: pk,
    name :: Text,
    dateOfBirth :: Date
  }
  deriving stock (Eq, Show, Generic, Functor, Foldable, Traversable)
  deriving anyclass (FromJSON, ToJSON)

Here, the idea is not to use the full breadth of available types for pk. It is intended to be used for two types: unit (()) and RecordId (a type modeling a primary key for the given database table). Instead of being a reusable wrapper, DatabaseRecord is only intended as being reused in two versions DatabaseRecord (), and DatabaseRecord RecordId: one version is meant to represent a row prior to insertion, when the primary key is not yet known. The other represents a full record after insertion, where we know the generated primary key.

This is merely a shift of focus from the first example. We’re still using a type parameter to make a field polymorphic. Doing so, we still get typeclasses instances for free. Note that the aeson instances, while available through generics, may not make sense in all contexts (ignoring for a minute the fact that directly serializing a database row to JSON is usually a bad idea in actual codebases): For DatabaseRecord RecordId, the automatic derivation will serialize it as a JSON object, deferring to ToJSON RecordId for the contents of recordId.

{
  "recordId": "01GJYP9AST5HSBJKBMJBNT28V2",
  "name": "Pink Floyd",
  "dateOfBirth": "1979-11-30"
}

For DatabaseRecord (), we would expect the recordId field to be either absent or set to null. Sadly, that is not what happens. Since recordId has type (), its JSON representation will be computed in accordance with ToJSON (), which is… []. This behaviour is surprising, but makes sense: a JSON array can be seen as a tuple, and the unit type can be seen as an empty tuple. So unit can be seen as an empty JSON array.

{
  "recordId": [],
  "name": "Pink Floyd",
  "dateOfBirth": "1979-11-30"
}

It is always possible to create a type that’s isomorphic to () and to give it a ToJSON instance that serializes to null, but that becomes tedious. Worse, the easiest thing to implement (just using () and generic-derivated instances) will give undesired behaviour.

The problem here is that we are using a very polymorphic type when we are only expecting to use it in two concrete implementations. The openness here is both a blessing and a curse: we get things for free, but we allow unwanted states to exist.

Step 2

Let’s take a step back and think about what we actually want. We don’t care about the actual type of the recordId field: when it is present, its shape is fixed. We mostly care about the context of whether it is there or not.

data DatabaseRecord (f :: Type -> Type) =
  DatabaseRecord {
    recordId :: f RecordId,
    name :: Text,
    dateOfBirth :: Date
  }

Here, we are not taking a regular type parameter, but rather a type constructor parameter (its kind is Type -> Type). This lets us pin the concrete RecordId type in the record definition. Now, what can f be? We want to cover two cases:

• there is a recordId
• there is no recordId

For the first case, we can use Identity (newtype Identity a = Identity { runIdentity :: a }). It acts as a wrapper around any a. More importantly, it fits the Type -> Type kind. So DatabaseRecord Identity provides us with what we want: a record carrying a primary key.

Now for the second case, we don’t want any value, but we still need the Type -> Type kind. For this, we can use the Proxy type. Defined as data Proxy a = Proxy, it carries a phantom type. a appears in the left-hand side of the declaration, but is absent from the right-hand side. This means that in Proxy a, the type a only appears at the type level. The actual value Proxy is a constructor with no arguments, so there is no value of type a actually carried at run time. This is used a lot with type-level programming, but here we are just trying to fullfil the Type -> Type kind without providing an actual value. So DatabaseRecord Proxy provides us with what we want: a record not carrying a primary key.

Another benefit of taking the context as a parameter instead of the actual type is that the context can be reused for different fields. Database rows usually carry a created_at field that is also populated when the row is inserted. With the f parameter, it can be added to the record definition with minimal fuss:

data DatabaseRecord (f :: Type -> Type) =
  DatabaseRecord {
    recordId :: f RecordId,
    name :: Text,
    dateOfBirth :: Date,
    createdAt :: f UTCTime
  }

Had we chosen the previous way to model DatabaseRecord, we would now have

data DatabaseRecord pk cat =
  DatabaseRecord {
    recordId :: pk,
    name :: Text,
    dateOfBirth :: Date,
    createdAt :: cat
  }

Using a type constructor as a parameter is a very convenient way to model the presence or absence of certain fields while still pinning the expected types of those fields, when they should be there. For one field, this is good because it makes the actual types clear, but it becomes really interesting when there are multiple fields with different types that share the same context.

The flip side, as always when moving with more constrained solutions, is that we reduce polymorphism and then cannot benefit from what it provides. Here it’s not possible to automatically derive typeclasses: we have to hold GHC’s hand:

{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE UndecidableInstances #-}

…

deriving instance (Show (f RecordId), Show (f UTCTime))  => Show (D f)

Also, we have pinned the concrete type of the primary key and the creation date. However, the f type constructor is still unconstrained, so we can still model DatabaseRecord [] or DatabaseRecord (ContT Void (Coyoneda (Cotambara (Tannen Identity (Kleisly IO))) Int)) (for instance).

Step 3: Trees That Grow (or just branches, maybe?)

This is where we bring out the big guns. The Trees That Grow paper describes a mechanism that lets us do exactly what we want: explicitly choosing types based on the context, at the small cost of using a few advanced haskell features.

The idea here is to start by listing the contexts we care about:

{-# LANGUAGE DataKinds #-}

data DbContext = BeforeInsertion | AfterInsertion

With the help of DataKinds, this humble enum is promoted to the realm of types: DbContext can be used as a kind, in addition to a type, and the constructors 'BeforeInsertion and 'AfterInsertion (note the leading quotes: while not strictly required, they let us make it explicit when using types promoted from data constructors) are created as types in addition to BeforeInsertion and AfterInsertion being terms.

So this lets us have an enum at the type level, describing the context we are in. So (slight spoiler) we will define DatabaseRecord as data DatabaseRecord (context :: DbContext) = …. This way, We can only talk about DatabaseRecord BeforeInsertion and DatabaseRecord AfterInsertion.

Next is to decide the actual types of the recordId and createdAt fields. We cannot do this inside the definition of DatabaseRecord. What we need to do is to define something like a function: DbContext -> Type, that operates at the type level. With the help of another extension (TypeFamilies), we can do just that:

type family RecordIdType (context :: DbContext) where
  RecordIdType BeforeInsertion = ()
  RecordIdType AfterInsertion = RecordId

type family CreatedAtType (context :: DbContext) where
  CreatedAtType BeforeInsertion = ()
  CreatedAtType AfterInsertion = UTCTime

And finally, we can define our brand new DatabaseRecord:

data DatabaseRecord (context :: DbContext) =
  DatabaseRecord {
    recordId :: RecordIdType context,
    name :: Text,
    dateOfBirth :: Date,
    createdAt :: CreatedAtType context
  }

deriving instance (Show (RecordIdType context), Show (CreatedAtType context)) => Show (DatabaseRecord context)

All done! This is obviously the perfect solution, so you should use this technique everytime. I promise nothing bad will happen.

More seriously, this encoding is the tightest implementation of the problem statement. As you can see it is also a fairly complex one, and like before it requires manually declaring deriving instance dependencies.

What did we learn?

In a not-so-surprising turn of events, it appears that advanced type-level features give us more expressive power while making things more complex and applicable in fewer contexts.

“Simple” polymorphic records crop up a lot in day-to-day web programming and are very effective at keeping APIs consistent. This pattern interacts nicely with automatic deriving, especially for JSON instances. For better or worse, it also doesn’t prevent us developers from modeling nonsensical types.

Taking type constructors (of kind Type -> Type) as a type parameter is surprisingly effective at modeling context-dependent data requirements. Higher kinded types have a scary reputation outside Haskell, but they can have concrete use-cases.

Finally, sophisticated techniques such as trees that grow are definitely not something one would use every day, but they can be extremely effective at reducing redundancy in complex data modeling. Seeing such advanced mechanisms all mesh together to give rise to a concrete use-case is part of what makes Haskell, Haskell.