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
?
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 ofShow1
as being declared roughly like this (see alsoshowsPrec1
):Here's another inaccurate-but-useful way to think about
Show1
. I'm using theconstraints
library's "entailment" operator to declare thatf a
should be an instance ofShow
whenevera
is. This model is a bit simpler but perhaps less practical.Anyway,
Fix :: (* -> *) -> *
is showable if its argument is a higher-order showable. From the source code:The authors of
recursion-schemes
could have usedStandaloneDeriving
to write theirShow
instance...... but this context requires
UndecidableInstances
.The easiest way to write a
Show1
instance for a given functor is to use thederiving-compat
library's Template Haskell helper.This'll generate the following instances,
giving you exactly what you want for
Labeled
's derived instance:(PS. Have you considered using a library like
bound
to manage names and binders in your term language?)