如何用 GADT 表示变量类型的构造函数列表？

Question

我正在为我参与的研究项目实现一个小型 DSL。由于这是几乎所有对 GADT 的解释的示例，我认为现在是真正开始使用它们的好时机。显而易见的表达式（算术等）运行良好，但我的 DSL 需要支持用户定义的函数，这是我运行遇到问题的地方。

没有 GADT，我的表达式类型的结构看起来有点像这样（浓缩为一个最小的例子）：

data Expr = IntConst Int
          | BoolConst Bool
          | Plus Expr Expr
          | Times Expr Expr -- etc
          | AndAlso Expr Expr -- etc
          | Call String [Expr] -- function call!

转换为GADT，如何表达Call规则？

data Expr a where
     IntConst :: Int -> Expr Int
     BoolConst :: Bool -> Expr Bool
     Plus :: Expr Int -> Expr Int -> Expr Int
     Times :: Expr Int -> Expr Int -> Expr Int
     AndAlso :: Expr Bool -> Expr Bool -> Expr Bool
     Call :: ???

我的第一个想法是，如果没有一些超级奇特的依赖类型，这是不可能的，因为没有办法知道给定的用户函数将接受什么类型（也是 return 类型，但我可以通过制作 Call return Expr a 并专注于建筑工地）。我可以通过添加规则

强制它按"erasing"类型进行类型检查

     EraseInt :: Expr Int -> Expr a
     EraseBool :: Expr Bool -> Expr a

但后来我似乎失去了拥有 GADT 的好处。我也在想可能还有一些其他的 rankN 多态性我可以在 Call 中使用（某种存在类型？），但我想出的任何东西似乎都不起作用。

帮忙？

Answer 1

您可以使用类型级列表创建另一个具有表示参数列表的 GADT，如下所示：

{-# LANGUAGE GADTs           #-}
{-# LANGUAGE KindSignatures  #-}
{-# LANGUAGE DataKinds       #-}
{-# LANGUAGE TypeOperators   #-}
{-# LANGUAGE PatternSynonyms #-}

data ArgList (as :: [*]) where
  NilArgList :: ArgList '[]
  ConsArg    :: Expr a -> ArgList as -> ArgList (a ': as)

data Expr a where
  IntConst  :: Int -> Expr Int
  BoolConst :: Bool -> Expr Bool
  Plus      :: Expr Int -> Expr Int -> Expr Int
  Times     :: Expr Int -> Expr Int -> Expr Int
  AndAlso   :: Expr Bool -> Expr Bool -> Expr Bool
  Call      :: String -> ArgList as -> Expr b

pattern x :^ y = ConsArg x y
infixr :^

example :: Expr Int
example =
  Call "exampleFn" (IntConst 1 :^ BoolConst True :^ NilArgList
                        :: ArgList [Int, Bool])

您需要为参数列表提供一些明确的类型签名（如 example）。此外，Call (forall b. Expr b) 的结果类型有点尴尬，但我不确定是否可以避免这种情况，除非你拥有比 String 更多的函数类型信息in。如果您在那里有更多信息，您还可以将参数类型 (as) 与函数的预期参数类型相关联。我认为我们需要有关具体情况的更多详细信息，但您必须进一步了解该部分。

Answer 2

也许你不需要为了你想要的东西而走依赖路线。将构建函数和调用函数分开的解决方案怎么样？这允许您在构建函数时键入函数，因此您可以进行类型检查调用。

data Expr a where
     IntConst  :: Int -> Expr Int
     BoolConst :: Bool -> Expr Bool
     Plus      :: Expr Int -> Expr Int -> Expr Int
     Times     :: Expr Int -> Expr Int -> Expr Int
     AndAlso   :: Expr Bool -> Expr Bool -> Expr Bool
     Fun       :: String -> Expr (a->b)
     Call      :: Expr (a->b) -> Expr a -> Expr b

-- type checks
test = Call (Fun "f" :: Expr (Int -> Int)) (IntConst 1)

-- doesn't type check
test' = Call (Fun "f" :: Expr (Int -> Int)) (BoolConst False)

对于具有多个参数的函数，您可以通过多次调用以柯里化的方式工作，即

 Call (Call (Fun "f" :: Expr (Int->Int->Int)) (IntConst 1)) (IntConst 1)

或者您可以用您的语言实现元组。

如何用 GADT 表示变量类型的构造函数列表？

How to represent a variable-typed constructor list with GADTs?

haskell

gadt