Deriving Bifunctor with Generics

综合技术 ( ) (源链)

Recently, I’ve been experimenting with deriving various type class instances generically, and seeing how far we can go before having to resort to TemplateHaskell. This post is a showcase of one such experiment: deriving Bifunctor
, a type class that ranges over types of kind * -> * -> *
, something GHC.Generics
is known not to be well suited for. The accompanying source code can be found in this gist

The problem

The GHC.Generics
module defines two representations: Generic
and Generic1
. The former is used to describe types of kind *
, while the latter is used for * -> *
. For example, the Generic1
representation is used in the generic-deriving
package’s Functor derivation.

class GFunctor (f :: * -> *) where
gmap :: (a -> b) -> f a -> f b

Then instances are defined for the generic building blocks. Whenever we have a GFunctor (Rep1 f)
, we can turn that into a Functor f

With this, it’s possible to derive many useful instances of classes that range over *
or * -> *
. However, there’s no Generic2
, so if we try to adapt generic-deriving
’s Functor approach to Bifunctors, we’ll run into problems.

class Bifunctor (p :: * -> * -> *) where
bimap :: (a -> b) -> (c -> d) -> p a c -> p b d

The type parameter p
takes two arguments, but the generic Rep
and Rep1
representations are strictly * -> *
(in the case of Rep
, the type parameter is phantom – it’s only there so that much of the structure of Rep
and Rep1
can be shared, and Rep1
requires * -> *
). This means that even if we defined a GBifunctor
, we would need to require a GBifunctor (Rep2 p)
which we could then turn into a Bifunctor p
. Alas, Rep2
doesn’t exist.

Indeed, the deriving mechanism in the bifunctors package uses TH.

The solution

The solution is inspired by how lenses implement polymorphic updates. The idea is that a Lens s t a b
focuses on the a
inside some structure s
, and if we swap that a
with a b
, we get a t

Since we’re talking about Bifunctors now, we need two more type variables:

class GBifunctor s t a b c d where
gbimap :: (a -> b) -> (c -> d) -> s x -> t x

and t
will be the generic representations, which means they are of kind * -> *
. However, we’re going to be using Generic
instead of Generic1
, so the type parameter x
is not used.

Unlike the GFunctor
class, which looked exactly like Functor
, this one is a lot different from Bifunctor
. Also important to note that gbimap
’s type signature is more polymorphic than that of bimap
, so we need to ensure that our instances are properly parametric.

In an earlier version of this class, I had functional dependencies on the class that expressed this interrelation between the type variables, but I had to lose them so that more interesting instances could be defined (more on this later).

The boring instances

The first instance simply looks through the metadata node.

instance GBifunctor s t a b c d
=> GBifunctor (M1 k m s) (M1 k m t) a b c d where

gbimap f g = M1 . gbimap f g . unM1

A sum l :+: r
can be turned into l' :+: r'
if we can turn l
into l'
and r
into r'

( GBifunctor l l' a b c d
, GBifunctor r r' a b c d
) => GBifunctor (l :+: r) (l' :+: r') a b c d where

gbimap f g (L1 l) = L1 (gbimap f g l)
gbimap f g (R1 r) = R1 (gbimap f g r)

And similarly, for products.

( GBifunctor l l' a b c d
, GBifunctor r r' a b c d
) => GBifunctor (l :*: r) (l' :*: r') a b c d where

gbimap f g (l :*: r) = gbimap f g l :*: gbimap f g r

The last boring instance is for unit types, these are trivially Bifunctors.

instance GBifunctor U1 U1 a b c d where
gbimap _ _ = id

Incoherent instances

With all of the gluing out of the way, we can now get to the meat of the problem: the actual fields in the constructors. When considering a field, we have 3 cases:

The field is of type a
, and we apply the first function to turn it into a b

instance {-# INCOHERENT #-} GBifunctor (Rec0 a) (Rec0 b) a b c d where
gbimap f _ (K1 a) = K1 (f a)

Similarly, if it’s a c
, we turn it into a d
using the second function.

instance {-# INCOHERENT #-} GBifunctor (Rec0 c) (Rec0 d) a b c d where
gbimap _ g (K1 a) = K1 (g a)

Finally, the field is neither a
, nor c
, so we just leave it alone.

instance {-# INCOHERENT #-} GBifunctor (Rec0 x) (Rec0 x) a b c d where
gbimap _ _ = id

Note that these instances need to be defined with {-# INCOHERENT #-}
pragmas. This is required because neither of (Rec0 a) (Rec0 b) a b c d
and (Rec0 c) (Rec0 d) a b c d
is more specific than the other.

However, in our case, this is not a problem, because we’re going to invoke instance resolution with polymorphic arguments, so there will be exactly one instance that matches.

Default signatures

We can now revise our original class definition, and add a default signature ( DefaultSignatures
). This will make Bifunctor
derivable with DeriveAnyClass

class Bifunctor p where
bimap :: (a -> b) -> (c -> d) -> p a c -> p b d

default bimap
:: ( Generic (p a c)
, Generic (p b d)
, GBifunctor (Rep (p a c)) (Rep (p b d)) a b c d
) => (a -> b) -> (c -> d) -> p a c -> p b d
bimap f g = to . gbimap f g . from

Note the line GBifunctor (Rep (p a c)) (Rep (p b d)) a b c d
. Here’s where we establish the relationship between the types. This now allows us to derive a Bifunctor
instance for Either

deriving instance Bifunctor Either

For example, when looking at the Left
constructor, the compiler will try to find an instance for GBifunctor (Rec0 a) (Rec0 b) a b c d
. There is exactly one instance that matches this, so our incoherent instance will not bite us. This is important: if instead we wanted an instance for a concrete type, say, Either Int Int
, all of our incoherent instances would match, and an arbitrary one would be picked. However, we avoid this problem by ensuring that the instance is derived for the aformentioned polymorphic form.

With this, we have a correct implementation of bimap
for Either

>>> bimap show (+ 10) (Left 10)
Left "10"
>>> bimap show (+ 10) (Right 10)
Right 20

Even better, compiled with -O1
, all of the overhead from using generics is optimised away:

= @ a_a3EL @ b_a3EM @ c_a3EN @ d_a3EO f_X1EN g_X1EP eta_B1 ->
case eta_B1 of {
Left g1_a3X5 -> Left (f_X1EN g1_a3X5);
Right g1_a3X8 -> Right (g_X1EP g1_a3X8)

A few more instances

The above deriving mechanism is naive: it only looks at fields whose types is exactly a
or b
. But we can do better: what if the field is a Maybe a
? Surely we can turn that into a Maybe b
. Or if it’s an Either a b
, we can turn that into an Either c d
, since it has a Bifunctor

The following three instances do exactly that.

instance {-# INCOHERENT #-} Bifunctor f
=> GBifunctor (Rec0 (f a c)) (Rec0 (f b d)) a b c d where
gbimap f g (K1 a) = K1 (bimap f g a)

instance {-# INCOHERENT #-} Functor f
=> GBifunctor (Rec0 (f c)) (Rec0 (f d)) a b c d where
gbimap _ g (K1 a) = K1 (fmap g a)

instance {-# INCOHERENT #-} Functor f
=> GBifunctor (Rec0 (f a)) (Rec0 (f b)) a b c d where
gbimap f _ (K1 a) = K1 (fmap f a)

Now we can derive even more interesting Bifunctor

data T a b = T1 (Maybe a) a (Either a b) | T2 (Maybe b)
deriving (Generic, Bifunctor)


We have seen a technique for approximating a hypothetical Generic2
representation with only using Generic
. Of course there was nothing specific about the number 2, we can easily generalise this to any fixed number of parameters.

I’m planning on writing a post about a further generalisation of this idea, which allows us to talk about types that have an arbitrary number type parameters (unlike here, where it’s a fixed number), which I used in the generic-lens
library, to allow for type changing lenses over any type parameter (thanks to the more elaborate extra machinery, there is no need for incoherent instance resolution).

It would be interesting to see how far this can be pushed before hitting a roadblock that would truly require a bespoke GenericN

责编内容来自:( ) (源链) | 更多关于

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » Deriving Bifunctor with Generics

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录