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

Question

考虑：

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

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

如果我做类似的事情

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

指的是哪个Lit？Var Nothing此外，我想一次将其推广到多个绑定，但我不知道该怎么做。我遵循了优秀的 Edward Kmett绑定包中的一些示例，但现在我既困惑又迷茫。

score 9 · Accepted Answer

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

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

我认为这里发生的事情Maybe是被用来计算活页夹。SoNothing等价于 0 并指代最近的绑定器，Just Nothing等价于 1 并指代下一个最近的活页夹，依此类推。

因此，在您的示例中， theV Nothing将指代Lit 1，而V (Just Nothing)将指代Lit 3.

1 回答 1