根据标准 Haskell 重写 GADT 代码？

Question

我一直在努力理解文章 The Operational Monad Tutorial by Heinrich Apfelmus, where he uses GADTs。作为脑力练习，我尝试重写他的代码示例，使它们不再使用 GADT。我做不到，现在我确定这是我的能力有限，还是根本问题。

在 r/haskell 上，Edward Kmett 指出“如果您有等级 N 类型，您始终可以通过 class 将 GADT 转换为最终 [原文如此] 无标签表示。"

但是如果我也不想使用 Rank N 类型怎么办？我想，我不得不牺牲一些东西，但我应该仍然能够做到。

所以，如果我愿意牺牲一些类型安全性，使用虚类型、typeclasses 等等，那么我可以编写一个 eval 函数用于表达式（有点）像下面的表达式，没有使用 LANGUAGE 扩展？

                           -- using GADTs :
data Expr = I Int  |       -- Int  -> Expr Int
            B Bool |       -- Bool -> Expr Bool
            Add Expr Expr  -- Expr Int -> Expr Int -> Expr Int
            Eq  Expr Expr  -- Expr 1   -> Expr a   -> Expr Bool

Answer 1

如果没有 GADT，我们需要一个 Value 求和类型，包含所有可能的结果。我们还需要使我们的评估函数部分或 return 类似于 Maybe Value.

data Value = VI Int | VB Bool

eval :: Expr -> Value
eval (I i) = VI i
eval (B b) = VB b
eval (Add e1 e2) = case (eval e1, eval e2) of
   (VI i1, VI i2) -> VI (i1+i2)
   _              -> error "runtime type error"
...

Answer 2

没有 GADT，你不知道 Expr 是否类型正确，所以你只能实现一个 eval，这可能会引发错误。

eval :: Expr -> Maybe (Either Int Bool)
eval (I n) = pure (Left n)
eval (B b) = pure (Right b)
eval (Add e1 e2) = do
  x1 <- eval e1
  x2 <- eval e2
  case (x1, x2) of
    (Left n1, Left n2) -> pure (Left (n1 + n2))
    _                  -> Nothing
eval (Eq e1 e2) = do
  x1 <- eval e1
  x2 <- eval e2
  case (x1, x2) of
    (Left  n1, Left n2)  -> pure (Right (n1 == n2))
    (Right b1, Right b2) -> pure (Right (b1 == b2))
    _                    -> Nothing

根据标准 Haskell 重写 GADT 代码？

Rewriting GADT code in terms of standard Haskell?

haskell

gadt