Haskell GADT 'Show'-实例类型-变量推导

Question

这个代码

{-# LANGUAGE GADTs #-}

data Expr a where
    Val :: Num a => a -> Expr a
    Eq :: Eq a => Expr a -> Expr a -> Expr Bool

eval :: Expr a -> a
eval (Val x) = x
eval (Eq x y) = (eval x) == (eval y)

instance Show a => Show (Expr a) where
    show (Val x) = "Val " ++ (show x)
    show (Eq x y) = "Eq (" ++ (show y) ++ ") (" ++ (show x) ++ ")"

编译失败，出现以下错误消息：

Test.hs:13:32: error:
    * Could not deduce (Show a1) arising from a use of `show'
      from the context: Show a
        bound by the instance declaration at test.hs:11:10-32
      or from: (a ~ Bool, Eq a1)
        bound by a pattern with constructor:
                   Eq :: forall a. Eq a => Expr a -> Expr a -> Expr Bool,
                 in an equation for `show'
        at test.hs:13:11-16
      Possible fix:
        add (Show a1) to the context of the data constructor `Eq'
    * In the first argument of `(++)', namely `(show y)'
      In the second argument of `(++)', namely
        `(show y) ++ ") (" ++ (show x) ++ ")"'
      In the expression: "Eq (" ++ (show y) ++ ") (" ++ (show x) ++ ")" Failed, modules loaded: none.

注释掉最后一行可以解决问题并检查 GHCi 中 Expr 的类型表明，GHC 实际上没有推断 Eq 是 Eq a => (Expr a) -> (Expr a) -> Expr Bool 类型，而是推断Eq a1 => (Expr a1) -> (Expr a1) -> Expr Bool 为 data Expr a where ...。这解释了错误消息，因为 instance Show a => Show (Expr a) where ... 不会强制 a1 成为 Show.

的实例

不过我不明白，为什么 GHC 选择这样做。如果我不得不猜测，我会说它与 Eq returning 一个值有关，它根本不依赖于 a，因此 GHC "forgetting" 关于 a，一次 Eq return 一个 Expr Bool。这是——至少是——这里发生了什么？

此外，是否有一个干净的解决方案？我尝试了几件事，包括尝试通过 InstanceSigs 和 ScopedTypeVariables 来 "force" 想要的类型，做这样的事情：

instance Show a => Show (Expr a) where
    show :: forall a. Eq a => Expr a -> String
    show (Eq x y) = "Eq (" ++ (show (x :: Expr a)) ++ ") (" ++ (show (y :: Expr a)) ++ ")"
    ...

，但没有成功。而且由于我仍然是 Haskell 新手，我什至不确定这是否能以某种方式工作，因为我最初猜测为什么 GHC 不推断 "correct"/desired 类型第一名。

编辑：

好的，所以我决定添加一个功能

extract (Eq x _) = x

到文件（没有类型签名），只是为了看看它会有什么 return 类型。 GHC 再次拒绝编译，但这一次，错误消息中包含一些有关 skolem 类型变量的信息。快速搜索得到 this question，这（我认为？）形式化了我认为的问题：一旦 Eq :: Expr a -> Expr a -> Expr Bool return 出现 Expr Bool，a 就消失了"out of scope"。现在我们没有关于 a 的任何信息，因此 extract 必须具有签名 exists a. Expr Bool -> a，因为 forall a. Expr Bool -> a 不会对每个 [=25] 都为真=].但是因为 GHC 不支持 exists，类型检查失败。

Answer 1

一个选项是不需要需要Show a超约束。

instance Show (Expr a) where
  showsPrec p (Eq x y) = showParen (p>9)
       $ ("Eq "++) . showsPrec 10 x . (' ':) . showsPrec 10 y

当然，这有点把石头踢掉了，因为现在你可以不写

  showsPrec p (Val x) = showParen (p>9) $ ("Val "++) . showsPrec 10 x

不再 - 现在叶值不受 Show 约束。但是在这里你可以通过使 Num 约束更强一点来解决这个问题：

data Expr a where
    Val :: RealFrac a => a -> Expr a
    Eq :: Eq a => Expr a -> Expr a -> Expr Bool
instance Show (Expr a) where
  showsPrec p (Val x) = showParen (p>9) $ ("Val "++)
          . showsPrec 10 (realToFrac x :: Double)

好吧，这是一个很大的技巧，到那时你还不如简单地使用

data Expr a where
    Val :: Double -> Expr Double
    Eq :: Eq a => Expr a -> Expr a -> Expr Bool

（或任何其他最适合您的数量要求的单一类型）。这不是一个好的解决方案。

要保留在 Expr 叶中存储 any 类型的数量的能力，但如果需要能够将它们限制为 Show，您需要在约束.

上多态
{-# LANGUAGE ConstraintKinds, KindSignatures #-} import GHC.Exts (Constraint) data Expr (c :: * -> Constraint) a where Val :: (Num a, c a) => a -> Expr a Eq :: Eq a => Expr a -> Expr a -> Expr Bool

那你可以做

instance Show (Expr Show a) where showsPrec p (Val x) = showParen (p>9) $ ("Val "++) . showsPrec 10 x showsPrec p (Eq x y) = showParen (p>9) $ ("Eq "++) . showsPrec 10 x . (' ':) . showsPrec 10 y

Answer 2

我只说明这一点

However I do not understand, why GHC chooses to do so.

问题是，可以编写带有 Num 和 Eq 实例的自定义类型，但没有 Show 实例。

newtype T = T Int deriving (Num, Eq) -- no Show, on purpose!

然后，此类型检查：

e1 :: Expr T
e1 = Val (T 42)

这样做：

e2 :: Expr Bool
e2 = Eq e1 e1

但是，应该清楚 e1 和 e2 不能被 show 编辑。要打印这些，我们需要 Show T，它丢失了。

此外，约束

instance Show a => Show (Expr a) where
      -- ^^^^^^

在这里没用，因为我们有 Show Bool，但这不足以打印 e2 :: Expr Bool.

这是存在类型的问题：一分钱一分货。当我们构建 e2 = Eq e1 e2 时，我们只需要 "pay" 约束 Eq T。因此，当我们模式匹配 Eq a b 时，我们只会得到 Eq t 返回（其中 t 是一个合适的类型变量）。我们不知道 Show t 是否成立。事实上，即使我们确实记住了 t ~ T，我们仍然缺少所需的 Show T 实例。

Haskell GADT 'Show'-实例类型-变量推导

Haskell GADT 'Show'- instance type-variable deduction

haskell

type-inference

gadt

type-variables