Instance of Show for instances of another class

Question

I have the following class:

class SappState s where
    getTable   :: s -> SymbolTable
    getStack   :: s -> Stack Scope
    getScopeId :: s -> ScopeNum
    getAst     :: s -> Program
    putTable   :: SymbolTable -> s -> s
    putStack   :: Stack Scope -> s -> s
    putScopeId :: ScopeNum    -> s -> s
    putAst     :: Program     -> s -> s

And I always show the datas that instance this class with the functions defined in it. So I generalized it with the following code:

instance (SappState s) => Show s where
    show st = showT ++ showS ++ showI ++ showA
        where
            showT = getTable st ++ "\n"
            showS = "Scope Stack:\n"  ++ getStack st ++ "\n"
            showI = "Scope Number:\t" ++ getScopeId st ++ "\n"
            showA = getAst st ++ "\n"

but GHC gives me the following error:

SappMonad.hs:87:27:
    Illegal instance declaration for `Show s'
      (All instance types must be of the form (T a1 ... an)
       where a1 ... an are *distinct type variables*,
       and each type variable appears at most once in the instance head.
       Use -XFlexibleInstances if you want to disable this.)
    In the instance declaration for `Show s'

Should I just use the FlexibleInstances pragma? I don't really understand what it does and if it's the right way or if I should drop the idea of generalizing the Show instance.

---

edit

I activated the pragma and it has this new error:

SappMonad.hs:88:10:
    Constraint is no smaller than the instance head
      in the constraint: SappState s
    (Use -XUndecidableInstances to permit this)
    In the instance declaration for `Show s'

I activated UndecidableInstances too and now a simple deriving Show will break:

data Architecture = Arch
    { archName :: String
    , types    :: Map.Map DataType Bytes
    } deriving (Show)

throws the following error:

SappMonad.hs:39:17:
    Overlapping instances for Show (Map.Map DataType Bytes)
      arising from the 'deriving' clause of a data type declaration
    Matching instances:
      instance (Show k, Show a) => Show (Map.Map k a)
        -- Defined in `containers-0.5.0.0:Data.Map.Base'
      instance SappState s => Show s -- Defined at SappMonad.hs:89:10
    When deriving the instance for (Show Architecture)

---

second edit

I googled some more in the subject and found OverlappingInstances, added the pragma and it compiles and I think it works correctly. But I feel I'm going too far with these language extensions. How could I stop using some of them and still get the same functionality?

Answer 1

Unfortunately there's no really clean solution for this problem.

The biggest downside of your current approach is if there is any similar "automatic" instance of Show anywhere in the program, they will both stop working completely and you'll get an error about "duplicate instances".

The fundamental issue is that instance resolution works by first matching against the right-hand side of instance declarations first. If there's a match, the machinery commits to that declaration and then goes and tries to resolve anything required by the left-hand side.

So in your case, searching for an instance for Show Foo for any Foo will match against your instance unconditionally, and then resolution will fail if it doesn't find a SappState Foo instance.

OverlappingInstances mitigates this slightly, as it will look for more specific instances first. So Show Int will resolve using the normal instance because that specifically mentions Int. But if there was something like instance SappState2 a => Show a also in scope, then any Foo without a more specific instance will lead to a duplicate instance error.

I would recommend getting implementers of SappState to write a Show instance by hand. You can mitigate the cost by providing a utility function showSappState :: SappState a => a -> String so that their instances can be just

instance Show Foo where
    show = showSappState

[A proper implementation of Show has a few more methods, but the same general approach applies]

If you want to be sure that all instances of SappState are also instances of Show, you can use a superclass to enforce this:

class Show a => SappState a where
    ...

There are actually a few proposals around to make it possible to automatically implement superclasses, which would solve your problem perfectly, but there's nothing implemented in GHC yet. One example is IntrinsicSuperclasses.

For completeness, it's worth mentioning that UndecidableInstances is somewhat dangerous because it can lead to instance resolution not terminating. The rules that guarantee that it will terminate are necessarily somewhat conservative since the problem is Turing complete, and in some cases like this they need to be turned off.

The problem with instance SappState a => Show a is that it reduces a Show a constraint to a SappState a constraint, and there's no obvious "progress" being made as the new instance being searched for is the same size as the old one. Imagine what could happen if someone also wrote instance Show a => SappState a.