Haskell Labeled AST: No instance for (Show1 (Label a)), How to construct an instance?

Question

I want to have an annotated AST, so I defined those recursive data structures using Fix:

data Term a 
  = Abstraction Name a
  | Application a a
  | Variable Name
  deriving (Read,Show,Eq,Functor,Foldable,Traversable)

data Label a b 
  = Label a (Term b)
  deriving (Read,Show,Eq,Functor,Foldable,Traversable)

newtype Labeled a 
  = Labeled (Fix (Label a))
  deriving (Show)

I want to be able to show a Labeled a, but the compiler is not happy:

No instance for (Show1 (Label a))  
arising from the first field of `Labeled' (type `Fix (Label a)')

What is the class Show1 and how do I define the appropriate instance to be able to show the Labeled a ?

Answer 1

Show1 is the class of what you might call "higher-order showables": type constructors which are showable whenever their argument is showable. For the purposes of fast-and-loose reasoning, you can think of Show1 as being declared roughly like this (see also showsPrec1):

class Show1 f where
    show1 :: Show a => f a -> String

Here's another inaccurate-but-useful way to think about Show1. I'm using the constraints library's "entailment" operator to declare that f a should be an instance of Show whenever a is. This model is a bit simpler but perhaps less practical.

class Show1 f where
    show1 :: Show a :- Show (f a)

Anyway, Fix :: (* -> *) -> * is showable if its argument is a higher-order showable. From the source code:

instance Show1 f => Show (Fix f) where
  showsPrec d (Fix a) =
    showParen (d >= 11)
      $ showString "Fix "
      . showsPrec1 11 a

The authors of recursion-schemes could have used StandaloneDeriving to write their Show instance...

deriving instance Show (f (Fix f)) => Show (Fix f)

... but this context requires UndecidableInstances.

The easiest way to write a Show1 instance for a given functor is to use the deriving-compat library's Template Haskell helper.

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
{-# LANGUAGE TemplateHaskell #-}

import Text.Show.Deriving
import Data.Functor.Foldable


type Name = String
data Term a 
    = Abstraction Name a
    | Application a a
    | Variable Name
    deriving (Read, Show, Eq, Functor, Foldable, Traversable)

deriveShow1 ''Term

data Label a b = Label a (Term b)
    deriving (Read, Show, Eq, Functor, Foldable, Traversable)

deriveShow1 ''Label

newtype Labeled a = Labeled (Fix (Label a)) deriving (Show)

This'll generate the following instances,

instance Show1 Term
instance Show a => Show1 (Label a)

giving you exactly what you want for Labeled's derived instance:

instance Show a => Show (Labeled a)

(PS. Have you considered using a library like bound to manage names and binders in your term language?)