Haskell étiqueté AST: Aucune instance pour (Show1 (Label a)), Comment construire une instance?

Question

Je veux avoir un AST annoté, donc je défini les structures de données récursives utilisant 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) 

Je veux être en mesure de show un Labeled a, mais le compilateur est pas heureux:

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

Qu'est-ce que class Show1 et comment ai-je défini l'instance appropriée pour pouvoir afficher le Labeled a?

Answer 1

Show1 est la classe de ce que vous pouvez appeler des "showables d'ordre supérieur": les constructeurs de type qui sont visibles chaque fois que leur argument est visible. Aux fins du raisonnement rapide et lâche, vous pouvez penser à Show1 comme étant déclaré à peu près comme celui-ci (voir aussi showsPrec1):

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

Voici une autre façon imprécise mais-utile de penser à Show1. J'utilise the constraints library"entailment" operator pour déclarer que f a devrait être une instance de Show chaque fois que a est. Ce modèle est un peu plus simple mais peut-être moins pratique.

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

Quoi qu'il en soit, Fix :: (* -> *) -> * est montrable si son argument est un montrable ordre supérieur. De the source code:

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

Les auteurs de recursion-schemes auraient pu utiliser StandaloneDeriving pour écrire leur exemple Show ...

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

... mais ce contexte, UndecidableInstances. La méthode la plus simple pour écrire une instance Show1 pour un foncteur donné est d'utiliser lede the deriving-compat library.

{-# 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) 

Cela va générer les cas suivants,

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

vous donnant exactement ce que vous voulez pour Labeled « s par exemple dérivé:.

instance Show a => Show (Labeled a) 

(PS Avez-vous envisagé d'utiliser un bibliothèque comme bound pour gérer les noms et les reliures dans votre langue maternelle?)