正确标记AST

Question

我一直试图建立标记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或者应用程序时.这是不可能的.考虑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索引(通过绑定).

Answer 1

如果您确实愿意，可以编写一个类型良好的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