In Haskell, type classes define operations with their type signatures. Many of them also define laws which must be satisfied by each of their instances. As laws can’t be checked by the compiler, writing new instances is a potentially dangerous operation. We have various options for assuring our hand-written instances are law-abiding such as pen-and-paper reasoning, and property-based testing.

A compelling alternative is to have the compiler write the instances for us: this is known as deriving instances. To this end, GHC implements several strategies such as DeriveFunctor and DeriveAnyClass. The most recent addition DerivingVia is based on the concept of isomorphisms. The idea is simple: to derive an instance for type A, look at some isomorphic type B and reuse its instance, inserting conversions between A and B where they are needed.

By design, DerivingVia operates only on a single isomorphism: coerce, which converts between types with the same runtime representation. The paper introducing the DerivingVia extension shows how to generalize the technique slightly and derive through the isomorphisms generated by GHC Generics. We will take this technique a step further and show how to derive instances through arbitrary isomorphisms. We refer to this as iso-deriving.

In this post I’ll present iso-deriving and show some examples of iso-deriving in action. I’ve packaged up all the types and classes used here in the iso-deriving package.

Isomorphisms

We say that two types A and B are isomorphic if there is a pair of functions f :: A -> B and g :: B -> A satisfying f . g = id and g . f = id.

For example:

• ByteString is isomorphic to [Word8] using pack and unpack
• Integer is isomorphic to itself using (+ 2) and (- 2)
• (a, b) is isomorphic to (b, a) using swap and swap

The following type class captures the fact that a and b are isomorphic.

class Isomorphic a b  where
  inj :: a -> b
  prj :: b -> a

Instances should satisfy inj . prj = id and prj . inj = id.

Passing around an isomorphism

To iso-derive instances for a, we will need to pick some isomorphic type b and pass it along in the deriving clause. We will define a newtype wrapper for this:

type As :: Type -> Type -> Type
newtype As a b = As b

A value of type As a b is represented at runtime as b, but can be converted to a (and back) with no loss of information.

We will also need such wrappers for higher-kinded types:

type As1 :: (k -> Type) -> (k -> Type) -> k -> Type
newtype As1 f g a = As1 (g a)

type As2 :: (k1 -> k2 -> Type) -> (k1 -> k2 -> Type) -> k1 -> k2 -> Type
newtype As2 f g a b = As2 (g a b)

We will need a special “wrapper” instance for each class we want to derive isomorphically. Much like the instances generated by DerivingVia, these all follow a strict mechanical pattern. Here is the instance for Num:

instance (Isomorphic a b, Num a) => Num (As a b) where

  (As x) + (As y) = As $ inj @a @b $
    prj @a @b x + prj @a @b y

  (As x) * (As y) = As $ inj @a @b $
    prj @a @b x * prj @a @b y

  signum (As x) = As $ inj @a @b $
    signum (prj @a @b x)

  abs (As x) = As $ inj @a @b $
    abs (prj @a @b y)

  fromInteger x = As $ inj @a @b $
    fromInteger x

We’re omitting some methods for brevity, but they follow the same pattern. Note the use of -XTypeApplications to make the choice of inj and prj unambiguous¹.

The generation of these instances could be automated, but as we’ll only ever need one instance per class, it suffices to put them into the library. Here are some of the instances exported by iso-deriving:

instance (Isomorphic a b, Eq a)
  => Eq (As a b)

instance (Isomorphic a b, Ord a)
  => Ord (As a b)

instance (Isomorphic a b, Semigroup a)
  => Semigroup (As a b)

instance (Isomorphic a b, Monoid a)
  => Monoid (As a b)

instance (forall x . Isomorphic (f x) (g x), Functor f)
  => Functor (As1 f g)

instance (forall x . Isomorphic (f x) (g x), Applicative f)
  => Applicative (As1 f g)

instance (forall x . Isomorphic (f x) (g x), Monad f)
  => Monad (As1 f g)

instance (forall x y . Isomorphic (f x y) (g x y), Category f)
  => Category (As2 f g)

Now that we know how iso-deriving works, let’s take a look at some examples.

Points and Vectors

Here is a type representing 2D points:

data Point a = Point { x :: a, y :: a }

What instances might we want to derive? GHC will happily derive Eq, Show and Functor for us. However it won’t be able to give us Num or Applicative.

To derive Num and Applicative, we will use an isomorphism between Point a and a familiar type. While (a, a) is the obvious choice, it wouldn’t let us derive Applicative either. Instead, we will use Bool -> a.

We will also use Ap from Data.Monoid. Ap defines a Num instance lifted through a given applicative functor. That is (+) is implemented as liftA2 (+), negate as fmap negate, and so on. We will give our wrapper the name Squared to be able to refer to it later.

data Point a = Point { x :: a, y :: a }
  deriving (Eq, Show, Functor)

  deriving Num
    via (Squared a `As` Point a)

  deriving (Applicative, Monad)
    via (Squared `As1` Point)

type Squared = Ap ((->) Bool)

The compiler will ask us to fill in the missing isomorphism, which is straightforward.

instance Isomorphic (Squared a) (Point a) where
  prj (Point x y) = Ap $ \p -> if p then x else y
  inj (Ap f)      = Point (f True) (f False)

We still need to convince ourselves that we have provided a valid isomorphism. Fortunately, this is usually much simpler than verifying all the instance laws.

These instances behave in the expected way. Applicative works pointwise on the elements and Num is lifted through the Applicative.

>>> pure 2 :: Point Double
Point {x = 2, y = 2}

>>> Point 1 2 + Point 10 100
Point {x = 11, y = 102}

We can even do scalar multiplication:

>>> Point 1 2 * 2
Point {x = 2, y = 4}

Note how we were able to derive several instances for the price of just one isomorphism.

Counting elements

Let’s say we want a monoid describing whether a collection is empty or not.

data NoneOrMore
  = None
    -- ^ No elements
  | OneOrMore
    -- ^ At least one element

This monoid is akin to Any, mapping None to False and OneOrMore to True.

data NoneOrMore = None | OneOrMore
  deriving (Semigroup, Monoid)
    via (Any `As` NoneOrMore)

instance Isomorphic Any NoneOrMore where
  inj (Any False) = None
  inj (Any True)  = OneOrMore

  prj None        = Any False
  prj OneOrMore   = Any True

The default element is None and composition behaves like disjunction.

>>> mempty :: NoneOrMore
None

>>> (None, []) <> (OneOrMore, [1,2])
(OneOrMore, [1,2])

>>> mconcat [None, None]
None

>>> mconcat [None, OneOrMore, None]
OneOrMore

There is an isomorphism not between Any and All that maintains monoid structure, so we could also have defined NoneOrMore in terms of All.

Monads from transformers

The These type can be used to represent either or both of two values (but not neither).

data These a b = This a | That b | These a b
  deriving (Functor)

The these package defines an instance Semigroup a => Monad (These a). To develop an understanding for this instance, consider the isomorphism:

  These a b
= Either a (b, Maybe a)
= WriterT (Maybe a) (Either a) b

The Monad instance for These a is indeed the same as that of WriterT (Maybe a) (Either a). Therefore we can iso-derive Monad (These a).

data These a b = This a | That b | These a b
  deriving stock (Functor)
  deriving (Applicative, Monad)
    via (TheseMonad a `As1` These a)

type TheseMonad a = WriterT (Maybe a) (Either a)

instance Isomorphic (TheseMonad a b) (These a b) where
  prj (This a)    = WriterT (Left a)
  prj (That b)    = WriterT (Right (b, Nothing))
  prj (These a b) = WriterT (Right (b, Just a))

  inj (WriterT (Left a))             = This a
  inj (WriterT (Right (b, Nothing))) = That b
  inj (WriterT (Right (b, Just a)))  = These a b

A nice thing about this is that the implementation details involving transformers are hidden away. Users of our type will see:

data These a b = This a | These a b | That b

instance Functor (These a)
instance Semigroup a => Applicative (These a)
instance Semigroup a => Monad (These a)

And it works in the expected way:

>>> pure 2 :: These () Integer
That 2

>>> do { a <- These "warning!" 1; b <- That 2; pure (a + b) }
These "warning!" 3

>>> do { a <- This "error!"; b <- That 2; pure (a + b) }
This "error!"

Performance

Iso-deriving inserts inj and prj in the definition of type class methods. The performance of iso-derived instances depends on the performance of inj and prj. Sometimes, GHC will optimise inj and prj away, but you shouldn’t count on it. If performance is an issue, you want your instances to be hand-written instead.

Conclusion

Iso-deriving is a lightweight technique for deriving lawful instances of any type class with minimal effort. It allows very quick exploration of the space of potential instances, especially when performance is not critical. Please try it out for yourself and let me know what use cases you find for iso-deriving!