The evolution of: Decoupling base and GHC

23

Sure you could. It needs trickery to make it appear instances are in a strict substitution ordering. So you end up with difficult-to-follow code (untested):

instance {-# OVERLAPPING #-} Functor f => (:<:) f f where
  inj = id

instance {-# OVERLAPPABLE #-} (Functor f, Functor g', SubT' f g') => (:<:) f g' where
  inj = inj'

class (Functor sub, Functor sup) => SubT' sub sup  where
  inj' :: sub a -> sup a

instance {-# OVERLAPPING #-} (Functor f, Functor g) => SubT' f (f :+: g) where
  inj = Inl

instance {-# OVERLAPPABLE #-} (Functor f, Functor g, Functor h, (:<:) f h) => SubT' f (g :+: h) where
  inj' = Inr . inj

(Needs UndecidableInstances.)

One of the limitations with Swiestra’s approach is that the tree is right-biased. (The instances don’t try to recurse to the left of (:+:) like (f :+: f') :+: (g :+: g'). [2008 JFP paper, middle of 2nd page of Section 4 “may fail to find an injection”.]) This technique can be expanded to cope with that. (You need two auxiliary SubT classes; and you need to choose which direction to prefer first. The instances get pretty ugly.)

You mean that feature that we do not have? And do not need?

Yes. In particular are there any ‘partially overlapping’ instances?:

instance C a Bool  ...
instance C Int b  ...

Allowing that really hampers GHC sharpening up its act on overlaps. And I suspect nobody actually wants it. (Or if they do, the above technique can handle it, at cost of forcing a choice.)

1 Like