在 GADT 上定义类型 class 实例

Question

考虑以下代码

{-# LANGUAGE DataKinds             #-}
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE GADTs                 #-}
{-# LANGUAGE KindSignatures        #-}
{-# LANGUAGE MultiParamTypeClasses #-}

module Test where

data Nat
    = Z
    | S Nat
    deriving Show

data Test foo (n :: Nat) where
    Final :: Test foo n
    Step :: foo n -> Test foo (S n) -> Test foo n

instance Show (foo n) => Show (Test foo n) where
    show Final           = "final"
    show (Step bar step) = show bar ++ show step

其中 Test 是依赖于类型参数 foo 的 GADT，其类型为 Nat -> *.

上面的代码无法编译，出现以下错误

• Could not deduce (Show (foo ('S n))) arising from a use of ‘show’
  from the context: Show (foo n)
    bound by the instance declaration at src/Test.hs:18:10-42
• In the second argument of ‘(++)’, namely ‘show step’
  In the expression: show bar ++ show step
  In an equation for ‘show’:
         show (Step bar step) = show bar ++ show step
   |
20 |     show (Step bar step) = show bar ++ show step
   |                                        ^^^^^^^^^

我如何声明 Show (foo n) 对每个 n 成立，以便编译器在查找 Show (foo (S n)) 时接受它？

Answer 1

我认为这是一种自然的方式：

class ShowAllNats f where showNat :: f (n :: Nat) -> String
instance ShowAllNats foo => Show (Test foo n) where
    show Final = "final"
    show (Step bar step) = showNat bar ++ show step

可以通过存在量化来避免额外的类型class：

data Some f where Some :: f (n :: Nat) -> Some f
instance Show (Some foo) => Show (Test foo n) where
    show Final = "final"
    show (Step bar step) = show (Some bar) ++ show step

在 GADT 上定义类型 class 实例

defining type class instance on GADT

haskell

typeclass

gadt