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^{1}.

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!

- Certain type classes don’t need both sides of the bijection. For example
`Show`

,`Eq`

and`Ord`

could work with just the projection, while`Read`

works with just the injection. The iso-deriving package defines superclasses capturing this.↩

## About the author

If you enjoyed this article, you might be interested in joining the Tweag team.