擦除类型参数的 GADT 的相等性
Equality for GADTs which erase type parameter
我无法为以下使用 GADT 实现的表达式的类型安全 DSL 实现 Eq 的实例。
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Eq a => Expr a -> Expr a -> Expr Bool
表达式可以是 Bool 或 Int 类型。文字 Bool 和 Num 的构造函数具有相应的类型。只有Int个表达式可以相加（构造函数Plus）。 If 表达式中的条件应具有类型 Bool 而两个分支应具有相同的类型。还有一个相等表达式Equal，其操作数的类型应该相同，相等表达式的类型为Bool.
我对此 DSL 实施解释器 eval 没有任何问题。它的编译和工作就像一个魅力：
eval :: Expr a -> a
eval (Num x) = x
eval (Bool x) = x
eval (Plus x y) = eval x + eval y
eval (If c t e) = if eval c then eval t else eval e
eval (Equal x y) = eval x == eval y
但是，我很难为 DSL 实现 Eq 的实例。我尝试了简单的句法相等：
instance Eq a => Eq (Expr a) where
Num x == Num y = x == y
Bool x == Bool y = x == y
Plus x y == Plus x' y' = x == x' && y == y'
If c t e == If c' t' e' = c == c' && t == t' && e == e'
Equal x y == Equal x' y' = x == x' && y == y'
_ == _ = False
它没有进行类型检查（with ghc 8.6.5），错误如下：
[1 of 1] Compiling Main ( Main.hs, Main.o )
Main.hs:17:35: error:
• Could not deduce: a2 ~ a1
from the context: (a ~ Bool, Eq a1)
bound by a pattern with constructor:
Equal :: forall a. Eq a => Expr a -> Expr a -> Expr Bool,
in an equation for ‘==’
at Main.hs:17:3-11
‘a2’ is a rigid type variable bound by
a pattern with constructor:
Equal :: forall a. Eq a => Expr a -> Expr a -> Expr Bool,
in an equation for ‘==’
at Main.hs:17:16-26
‘a1’ is a rigid type variable bound by
a pattern with constructor:
Equal :: forall a. Eq a => Expr a -> Expr a -> Expr Bool,
in an equation for ‘==’
at Main.hs:17:3-11
Expected type: Expr a1
Actual type: Expr a2
• In the second argument of ‘(==)’, namely ‘x'’
In the first argument of ‘(&&)’, namely ‘x == x'’
In the expression: x == x' && y == y'
• Relevant bindings include
y' :: Expr a2 (bound at Main.hs:17:25)
x' :: Expr a2 (bound at Main.hs:17:22)
y :: Expr a1 (bound at Main.hs:17:11)
x :: Expr a1 (bound at Main.hs:17:9)
|
17 | Equal x y == Equal x' y' = x == x' && y == y'
|
我认为原因是构造函数 Equal“忘记”了其子表达式的类型参数 a 的值，并且类型检查器无法确保子表达式 x 和 y 都具有相同的类型 Expr a.
我尝试向 Expr a 添加一个类型参数以跟踪子表达式的类型：
data Expr a b where
Num :: Int -> Expr Int b
Bool :: Bool -> Expr Bool b
Plus :: Expr Int b -> Expr Int b -> Expr Int b
If :: Expr Bool b -> Expr a b -> Expr a b -> Expr a b
Equal :: Eq a => Expr a a -> Expr a a -> Expr Bool a
instance Eq a => Eq (Expr a b) where
-- same implementation
eval :: Expr a b -> a
-- same implementation
这种方法对我来说似乎不可扩展，一旦添加了具有不同类型子表达式的构造函数。
所有这些让我觉得我确实错误地使用了 GADT 来实现这种 DSL。有没有办法为这种类型实现 Eq ？如果不是，在表达式上表达这种类型约束的惯用方式是什么？
完整代码：
{-# LANGUAGE GADTs #-}
module Main where
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Eq a => Expr a -> Expr a -> Expr Bool
instance Eq a => Eq (Expr a) where
Num x == Num y = x == y
Bool x == Bool y = x == y
Plus x y == Plus x' y' = x == x' && y == y'
If c t e == If c' t' e' = c == c' && t == t' && e == e'
Equal x y == Equal x' y' = x == x' && y == y'
_ == _ = False
eval :: Expr a -> a
eval (Num x) = x
eval (Bool x) = x
eval (Plus x y) = eval x + eval y
eval (If c t e) = if eval c then eval t else eval e
eval (Equal x y) = eval x == eval y
main :: IO ()
main = do
let expr1 = If (Equal (Num 13) (Num 42)) (Bool True) (Bool False)
let expr2 = If (Equal (Num 13) (Num 42)) (Num 42) (Num 777)
print (eval expr1)
print (eval expr2)
print (expr1 == expr1)
你的问题是在
Equal x y == Equal x' y' = ...
可能 x 和 x' 的类型不同。例如，Equal (Bool True) (Bool True) == Equal (Int 42) (Int 42) 类型检查，但我们不能像在 Eq 实例中尝试做的那样简单地比较 Bool True == Int 42。
这里有一些替代解决方案。最后一个（将==概括为eqExpr）对我来说似乎是最简单的，但其他的也很有趣。
使用单例和计算类型
我们从您的原始类型开始
{-# LANGUAGE GADTs #-}
module Main where
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Eq a => Expr a -> Expr a -> Expr Bool
并定义一个单例 GADT 来表示您拥有的类型
data Ty a where
TyInt :: Ty Int
TyBool :: Ty Bool
然后我们证明你的类型只能是Int或Bool，以及如何从表达式中计算它们。
tyExpr :: Expr a -> Ty a
tyExpr (Num _) = TyInt
tyExpr (Bool _) = TyBool
tyExpr (Plus _ _) = TyInt
tyExpr (If _ t _) = tyExpr t
tyExpr (Equal _ _) = TyBool
我们现在可以利用它并定义 Eq 实例。
instance Eq (Expr a) where
Num x == Num y = x == y
Bool x == Bool y = x == y
Plus x y == Plus x' y' = x == x' && y == y'
If c t e == If c' t' e' = c == c' && t == t' && e == e'
Equal x y == Equal x' y' = case (tyExpr x, tyExpr x') of
(TyInt, TyInt ) -> x == x' && y == y'
(TyBool, TyBool) -> x == x' && y == y'
_ -> False
_ == _ = False
使用 Typeable
我们对原来的GADT稍作修改：
import Data.Typeable
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: (Typeable a, Eq a) => Expr a -> Expr a -> Expr Bool
然后我们可以尝试将值转换为正确的类型：如果转换失败，我们有两个 Equal 属于不同的类型，因此我们可以 return False。
instance Eq (Expr a) where
Num x == Num y = x == y
Bool x == Bool y = x == y
Plus x y == Plus x' y' = x == x' && y == y'
If c t e == If c' t' e' = c == c' && t == t' && e == e'
Equal x y == Equal x' y' = case cast (x,y) of
Just (x2, y2) -> x2 == x' && y2 == y'
Nothing -> False
_ == _ = False
推广到异构平等
我们可以使用原来的GADT：
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Eq a => Expr a -> Expr a -> Expr Bool
并编写一个异构等式测试，即使两个表达式的类型不同也可以工作：
eqExpr :: Expr a -> Expr b -> Bool
eqExpr (Num x) (Num y) = x == y
eqExpr (Bool x) (Bool y) = x == y
eqExpr (Plus x y) (Plus x' y') = eqExpr x x' && eqExpr y y'
eqExpr (If c t e) (If c' t' e') = eqExpr c c' && eqExpr t t' && eqExpr e e'
eqExpr (Equal x y) (Equal x' y') = eqExpr x x' && eqExpr y y'
eqExpr _ _ = False
Eq实例是特例。
instance Eq (Expr a) where
(==) = eqExpr
最后的说明
正如 Joseph Sible 在评论中指出的那样，在所有这些方法中，我们不需要实例中的 Eq a 上下文。我们可以简单地删除它：
instance {- Eq a => -} Eq (Expr a) where
...
此外，原则上我们甚至不需要 Equal 定义中的 Eq a，因此我们可以简化我们的 GADT：
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Expr a -> Expr a -> Expr Bool
然而，如果我们这样做，eval :: Expr a -> a 的定义在 Equal 的情况下变得更加复杂，我们可能需要使用类似 tyExpr 的东西来推断类型，所以我们可以使用 ==.
我无法为以下使用 GADT 实现的表达式的类型安全 DSL 实现 Eq 的实例。
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Eq a => Expr a -> Expr a -> Expr Bool
表达式可以是 Bool 或 Int 类型。文字 Bool 和 Num 的构造函数具有相应的类型。只有Int个表达式可以相加（构造函数Plus）。 If 表达式中的条件应具有类型 Bool 而两个分支应具有相同的类型。还有一个相等表达式Equal，其操作数的类型应该相同，相等表达式的类型为Bool.
我对此 DSL 实施解释器 eval 没有任何问题。它的编译和工作就像一个魅力：
eval :: Expr a -> a
eval (Num x) = x
eval (Bool x) = x
eval (Plus x y) = eval x + eval y
eval (If c t e) = if eval c then eval t else eval e
eval (Equal x y) = eval x == eval y
但是，我很难为 DSL 实现 Eq 的实例。我尝试了简单的句法相等：
instance Eq a => Eq (Expr a) where
Num x == Num y = x == y
Bool x == Bool y = x == y
Plus x y == Plus x' y' = x == x' && y == y'
If c t e == If c' t' e' = c == c' && t == t' && e == e'
Equal x y == Equal x' y' = x == x' && y == y'
_ == _ = False
它没有进行类型检查（with ghc 8.6.5），错误如下：
[1 of 1] Compiling Main ( Main.hs, Main.o )
Main.hs:17:35: error:
• Could not deduce: a2 ~ a1
from the context: (a ~ Bool, Eq a1)
bound by a pattern with constructor:
Equal :: forall a. Eq a => Expr a -> Expr a -> Expr Bool,
in an equation for ‘==’
at Main.hs:17:3-11
‘a2’ is a rigid type variable bound by
a pattern with constructor:
Equal :: forall a. Eq a => Expr a -> Expr a -> Expr Bool,
in an equation for ‘==’
at Main.hs:17:16-26
‘a1’ is a rigid type variable bound by
a pattern with constructor:
Equal :: forall a. Eq a => Expr a -> Expr a -> Expr Bool,
in an equation for ‘==’
at Main.hs:17:3-11
Expected type: Expr a1
Actual type: Expr a2
• In the second argument of ‘(==)’, namely ‘x'’
In the first argument of ‘(&&)’, namely ‘x == x'’
In the expression: x == x' && y == y'
• Relevant bindings include
y' :: Expr a2 (bound at Main.hs:17:25)
x' :: Expr a2 (bound at Main.hs:17:22)
y :: Expr a1 (bound at Main.hs:17:11)
x :: Expr a1 (bound at Main.hs:17:9)
|
17 | Equal x y == Equal x' y' = x == x' && y == y'
|
我认为原因是构造函数 Equal“忘记”了其子表达式的类型参数 a 的值，并且类型检查器无法确保子表达式 x 和 y 都具有相同的类型 Expr a.
我尝试向 Expr a 添加一个类型参数以跟踪子表达式的类型：
data Expr a b where
Num :: Int -> Expr Int b
Bool :: Bool -> Expr Bool b
Plus :: Expr Int b -> Expr Int b -> Expr Int b
If :: Expr Bool b -> Expr a b -> Expr a b -> Expr a b
Equal :: Eq a => Expr a a -> Expr a a -> Expr Bool a
instance Eq a => Eq (Expr a b) where
-- same implementation
eval :: Expr a b -> a
-- same implementation
这种方法对我来说似乎不可扩展，一旦添加了具有不同类型子表达式的构造函数。
所有这些让我觉得我确实错误地使用了 GADT 来实现这种 DSL。有没有办法为这种类型实现 Eq ？如果不是，在表达式上表达这种类型约束的惯用方式是什么？
完整代码：
{-# LANGUAGE GADTs #-}
module Main where
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Eq a => Expr a -> Expr a -> Expr Bool
instance Eq a => Eq (Expr a) where
Num x == Num y = x == y
Bool x == Bool y = x == y
Plus x y == Plus x' y' = x == x' && y == y'
If c t e == If c' t' e' = c == c' && t == t' && e == e'
Equal x y == Equal x' y' = x == x' && y == y'
_ == _ = False
eval :: Expr a -> a
eval (Num x) = x
eval (Bool x) = x
eval (Plus x y) = eval x + eval y
eval (If c t e) = if eval c then eval t else eval e
eval (Equal x y) = eval x == eval y
main :: IO ()
main = do
let expr1 = If (Equal (Num 13) (Num 42)) (Bool True) (Bool False)
let expr2 = If (Equal (Num 13) (Num 42)) (Num 42) (Num 777)
print (eval expr1)
print (eval expr2)
print (expr1 == expr1)
你的问题是在
Equal x y == Equal x' y' = ...
可能 x 和 x' 的类型不同。例如，Equal (Bool True) (Bool True) == Equal (Int 42) (Int 42) 类型检查，但我们不能像在 Eq 实例中尝试做的那样简单地比较 Bool True == Int 42。
这里有一些替代解决方案。最后一个（将==概括为eqExpr）对我来说似乎是最简单的，但其他的也很有趣。
使用单例和计算类型
我们从您的原始类型开始
{-# LANGUAGE GADTs #-}
module Main where
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Eq a => Expr a -> Expr a -> Expr Bool
并定义一个单例 GADT 来表示您拥有的类型
data Ty a where
TyInt :: Ty Int
TyBool :: Ty Bool
然后我们证明你的类型只能是Int或Bool，以及如何从表达式中计算它们。
tyExpr :: Expr a -> Ty a
tyExpr (Num _) = TyInt
tyExpr (Bool _) = TyBool
tyExpr (Plus _ _) = TyInt
tyExpr (If _ t _) = tyExpr t
tyExpr (Equal _ _) = TyBool
我们现在可以利用它并定义 Eq 实例。
instance Eq (Expr a) where
Num x == Num y = x == y
Bool x == Bool y = x == y
Plus x y == Plus x' y' = x == x' && y == y'
If c t e == If c' t' e' = c == c' && t == t' && e == e'
Equal x y == Equal x' y' = case (tyExpr x, tyExpr x') of
(TyInt, TyInt ) -> x == x' && y == y'
(TyBool, TyBool) -> x == x' && y == y'
_ -> False
_ == _ = False
使用 Typeable
我们对原来的GADT稍作修改：
import Data.Typeable
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: (Typeable a, Eq a) => Expr a -> Expr a -> Expr Bool
然后我们可以尝试将值转换为正确的类型：如果转换失败，我们有两个 Equal 属于不同的类型，因此我们可以 return False。
instance Eq (Expr a) where
Num x == Num y = x == y
Bool x == Bool y = x == y
Plus x y == Plus x' y' = x == x' && y == y'
If c t e == If c' t' e' = c == c' && t == t' && e == e'
Equal x y == Equal x' y' = case cast (x,y) of
Just (x2, y2) -> x2 == x' && y2 == y'
Nothing -> False
_ == _ = False
推广到异构平等
我们可以使用原来的GADT：
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Eq a => Expr a -> Expr a -> Expr Bool
并编写一个异构等式测试，即使两个表达式的类型不同也可以工作：
eqExpr :: Expr a -> Expr b -> Bool
eqExpr (Num x) (Num y) = x == y
eqExpr (Bool x) (Bool y) = x == y
eqExpr (Plus x y) (Plus x' y') = eqExpr x x' && eqExpr y y'
eqExpr (If c t e) (If c' t' e') = eqExpr c c' && eqExpr t t' && eqExpr e e'
eqExpr (Equal x y) (Equal x' y') = eqExpr x x' && eqExpr y y'
eqExpr _ _ = False
Eq实例是特例。
instance Eq (Expr a) where
(==) = eqExpr
最后的说明
正如 Joseph Sible 在评论中指出的那样，在所有这些方法中，我们不需要实例中的 Eq a 上下文。我们可以简单地删除它：
instance {- Eq a => -} Eq (Expr a) where
...
此外，原则上我们甚至不需要 Equal 定义中的 Eq a，因此我们可以简化我们的 GADT：
data Expr a where
Num :: Int -> Expr Int
Bool :: Bool -> Expr Bool
Plus :: Expr Int -> Expr Int -> Expr Int
If :: Expr Bool -> Expr a -> Expr a -> Expr a
Equal :: Expr a -> Expr a -> Expr Bool
然而，如果我们这样做，eval :: Expr a -> a 的定义在 Equal 的情况下变得更加复杂，我们可能需要使用类似 tyExpr 的东西来推断类型，所以我们可以使用 ==.