haskell - Let 表达式在 AST 中如何工作？

Question

考虑:

data Expr a
  = V a
  | Lit Integer
  | Let (Expr a) (Expr (Maybe a))
    deriving (Eq,Show)

Let 构造函数使我能够绑定(bind)一个表达式(第一个参数)，以便在第二个表达式中引用它(V Nothing 引用它)。

如果我做类似的事情

Let (Lit 3) $ Let (Lit 1) $ Var Nothing

Var Nothing 指的是哪个Lit？此外，我想将其概括为一次多个绑定(bind)，我不知道该怎么做。我遵循了优秀的 Edward Kmett bound 的一些例子包，但现在我既困惑又迷失。

Answer 1

我稍微猜测一下，因为我以前没有见过这种绑定(bind)样式，但我认为 Maybe 类型有效地用于编码 de Bruijn indices .

基本思想是，对绑定(bind)变量的引用存储为一个数字，指定要经过的周围绑定(bind)器的数量才能到达相关绑定(bind)器。因此，例如 0 表示最接近的周围 Binder ，1 表示下一个最近的 Binder ，依此类推。

我认为这里发生的情况是，Maybe 被用来计算 Binder 数量。因此，Nothing 相当于 0，指的是最接近的 Binder ，Just Nothing 相当于 1，指的是下一个最接近的 Binder ，依此类推。

因此，在您的示例中，V Nothing 将引用 Lit 1，而 V (Just Nothing) 将引用 点燃3。