Instance implementation for in a class nested data type

Question

I'd like to know how instance Show could be implemented for Gmap data type presented in following code snippet Type families article without usage of deriving Show.

class GMapKey k where
  data GMap k :: * -> *
  empty       :: GMap k v
  lookup      :: k -> GMap k v -> Maybe v
  insert      :: k -> v -> GMap k v -> GMap k v

instance GMapKey Int where
  data GMap Int v        = GMapInt (Data.IntMap.IntMap v)
  empty                  = GMapInt Data.IntMap.empty
  lookup k   (GMapInt m) = Data.IntMap.lookup k m
  insert k v (GMapInt m) = GMapInt (Data.IntMap.insert k v m)

For this initiating implementation:

instance Show (GMap k v) where                                                                                                                                      
  show (GMapInt _) = undefined

compiler throws:

* Couldn't match type `k' with `Int'
  `k' is a rigid type variable bound by
    the instance declaration
    at /home/x/src/GMapAssoc.hs:27:10
  Expected type: GMap k v
    Actual type: GMap Int v
* In the pattern: GMapInt _
  In an equation for `show': show (GMapInt _) = undefined
  In the instance declaration for `Show (GMap k v)'
* Relevant bindings include
    show :: GMap k v -> String

Aside from the main question, I'd like to understand why compiler does not complain in this case:

instance Show (GMap k v) where                                                                                                                                      
  show _ = undefined

luqui luqui · Accepted Answer · 2018-01-22T07:11:03

You can't pattern match on a data constructor of a data family like GMap without already knowing it's key type -- i.e. it's not like a GADT, because it's open, so it would be impossible to cover all cases. So if you want to implement a generic show, you need to do it without accessing the representation directly. I have two alternatives for you:

Catch-all instance

After playing around a little, the simplest way I could come up with was to add a method to the class for use in the instance.

class GMapKey k where
  data GMap k :: * -> *
  empty       :: GMap k v
  lookup      :: k -> GMap k v -> Maybe v
  insert      :: k -> v -> GMap k v -> GMap k v
  showGMap    :: (Show v) => GMap k v -> String

Then you can make a single general catch-all instance.

instance (GMapKey k, Show v) => Show (GMap k v) where
  show = showGMap

This is a little less smooth than I would desire, but it's not too awfully bad. My main lament with this method is that it precludes deriving Show on the instances, i.e.

instance GMapKey Int where
  data GMap Int v        = GMapInt (Data.IntMap.IntMap v)
      deriving (Show)
  ...

is illegal because it overlaps with our catch-all instance. This could be kind of a pain if the type gets complex. The next method does not suffer from this problem.

Anyway, now we have an instance and can use it like usual.

example :: (GMapKey k, Show v) => GMap k v -> String
example gmap = show gmap

Dictionary method

If you need to use deriving Show, you could do it a more modern way using the constraints package.

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
import Data.Constraint

It also involves adding a method, but instead of returning a String, it returns a whole Show dictionary.

class GMapKey k where
  data GMap k :: * -> *
  empty       :: GMap k v
  lookup      :: k -> GMap k v -> Maybe v
  insert      :: k -> v -> GMap k v -> GMap k v
  showGMap    :: (Show v) => Dict (Show (GMap k v))

You can instantiate with deriving, and the showGMap instance is always the same.

 instance GMapKey Int where
   data GMap Int v        = GMapInt (Data.IntMap.IntMap v)
       deriving (Show)
   ...
   showGMap = Dict

(You could even use DefaultSignatures to avoid having to mention showGMap in the instances at all!)

Unfortunately, a catch-all instance will still overlap with this, and so we won't have a global Show instance for GMaps. However, we can manufacture one locally wherever we need it, using withDict

example :: forall k v. (GMapKey k, Show v) => GMap k v -> String
example gmap = withDict @k @v (show gmap)

which is annoying in a different way. Fortunately we only need to do this when we need a generic Show (GMap k v) instance -- if we already know what k is then the specific Show instances we derived will work.

Maybe there's a way to get the best of both worlds?

Instance implementation for in a class nested data type

2 Answers

Catch-all instance

Dictionary method