Haskell Labeled AST: No instance for (Show1 (Label a)), 如何构造实例？

Question

我想要一个带注释的 AST，所以我使用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)

我希望能够showa Labeled a，但编译器不高兴：

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

什么是类Show1以及如何定义适当的实例以显示Labeled a?

Answer 1

Show1是您可能称之为“高阶可显示对象”的类：只要其参数可显示，该类型构造函数就可显示。出于快速和宽松推理的目的，您可以认为Show1大致是这样声明的（另请参阅showsPrec1）：

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

这是另一种不准确但有用的思考方式Show1。我正在使用库constraints的“蕴涵”运算符来声明 that应该是每当是f a的一个实例。这个模型有点简单，但可能不太实用。Showa

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

无论如何，Fix :: (* -> *) -> *如果它的参数是高阶可显示的，则它是可显示的。从源代码来看：

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

作者本recursion-schemes可以用来StandaloneDeriving编写他们的Show实例......

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

...但是这个上下文需要UndecidableInstances.

为给定函子编写实例的最简单方法Show1是使用库deriving-compat的Template Haskell 帮助程序。

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

这将生成以下实例，

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

为您提供您想要的Labeled派生实例：

instance Show a => Show (Labeled a)

（PS。您是否考虑过使用类似的库bound来管理您的术语语言中的名称和活页夹？）