我一直在尝试构建标记的 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)。