6

我一直在尝试构建标记的 AST 一段时间。我们来介绍一下这个问题：

data E a
  = V a
  | LitInt Int
  | LitBool Bool
  | FooIntBool (E a) (E a) -- er…
    deriving (Eq,Show)

对我来说，那段代码的问题在于FooIntBool. 这个想法是它需要一个int表达式和一个bool表达式，并将它们粘合在一起。但E a可以是任何东西。鉴于上述定义，这将是有效的E：

FooIntBool (LitInt 3) (LitInt 0)

你可以看到问题。那么，我们想要什么？带标签的表达式。鉴于 E 的当前定义，这是不可能的，所以让我们介绍一些GADT：

data E :: * -> * -> * where
  V          :: a -> E l a
  LitInt     :: Int -> E Int a
  LitBool    :: Bool -> E Bool a
  FooIntBool :: E Int a -> E Bool a -> E (Int,Bool) a

这是相当不错的！我现在可以纠正这种代码：

FooIntBool (V "x") (LitBool False)

问题是当我想让它成为单子或应用程序时。这是不可能的。考虑 monad 的实现：

instance Monad (E l) where
  return = V

这是显而易见的，直截了当。让我们看看绑定实现：

  V x >>= f = f x -- obvious as well
  LitInt a >>= _ = LitInt a -- obvious yeah
  LitBool a >>= _ = LitBool a -- …
  FooIntBool a b >>= f = FooIntBool (a >>= ?) (b >>= ?) -- AH?

我们不能写a >>= f，b >>= f因为f :: a -> E l b. 我还没有找到解决这个问题的方法，我真的很好奇如何处理这个问题并且仍然能够使用 de Bruijn 索引（通过bound）。

4

2 回答 2

4

我认为您键入的 AST 不太可能按照您想要的方式工作。变量没有类型化的事实会受到伤害。试着想象用环境编写解释器会是什么样子；您必须在环境中查找变量，然后要么将结果转换为正确的类型，要么因错误而失败。所以我将建议一个稍微不同的带有类型变量的 AST，以及一个尚未解释的类型参数的重新排序。

data E v a where
  V          :: v a -> E v a
  LitInt     :: Int  -> E v Int
  LitBool    :: Bool -> E v Bool
  FooIntBool :: E v Int -> E v Bool -> E v (Int, Bool)

现在，据我所知，不可能为此定义一个守法的Monad实例。请注意，种类E是(* -> *) -> * -> *; 对于我们的目的而言，将其视为 可能更直观(* -> *) -> (* -> *)。Monad这在表面上与预期兼容* -> *，至少如果您部分适用E于 some v，但随后类型变得很奇怪。我相信您已经意识到这一点，这就是您将变量类型参数放在最后的原因；这样做的预期效果是(>>=)代表替代。但是，如果我们用我提出的这种新类型来做，它根本不兼容Monad。

不过，有一种不同的 monad 可以工作。我们可以将它的种类从* -> *to概括为(k -> *) -> (k -> *)（k在这种情况下只是*）。再次注意，我使用括号来强调，就像 , 的大多数实例一样Monad，E将被视为一元类型构造函数。我们将使用自然变换而不是任何旧的 Haskell 函数：

type a ~> b = forall x. a x -> b x

（顺便说一句，那种(~>)是(k -> *) -> (k -> *) -> *。）

要构造我们的新HMonad类型类，我们只需复制Monad并替换(->)为(~>). 有一个复杂性，就是我们必须翻转 的参数顺序(>>=)，以使类型起作用：

class HMonad m where
  hreturn ::  a ~> m a
  hbind   :: (a ~> m b) -> (m a ~> m b)

我将向您展示HMonad实例E，然后尝试对其进行解释：

instance HMonad E where
  hreturn = V
  hbind f e = case e of
    V v            -> f v
    LitInt x       -> LitInt x
    LitBool x      -> LitBool x
    FooIntBool a b -> FooIntBool (hbind f a) (hbind f b)

实际上，这看起来Monad与 AST 的无类型版本的实例完全一样。请注意，正如预期的那样，hreturn只是注入一个变量，并hbind通过查找变量并将函数应用于它们来执行一种类型安全的替换。这是由于较高等级的类型而起作用的。

你不能完全用 bound 包做到这一点，因为它使用Monad而不是这个 fancier HMonad。有可能（甚至已经多次完成）编写一个适用于像这样的类型化 AST 的 bound 版本，但尚不清楚它是否真的值得。

于 2014-07-05T15:17:23.253 回答
3

如果您真的想要，可以编写一个类型良好的Monad实例。我没有检查它是否遵循单子定律。

instance Monad (E l) where 
  return = V 

  V x >>= f = f x 
  LitInt a >>= _ = LitInt a 
  LitBool a >>= _ = LitBool a
  FooIntBool a b >>= f = FooIntBool (a >>= q.f) (b >>= r.f) where 

    q :: E (Int, Bool) t -> E Int t
    q (V x) = V x 
    q (FooIntBool x _) = x

    r :: E (Int, Bool) t -> E Bool t
    r (V x) = V x 
    r (FooIntBool _ x) = x
于 2014-07-03T20:57:07.747 回答