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)绑定包中得到了一些例子,但现在我既困惑又迷失了.

Answer 1

我有点猜测,因为我之前没有看过这种绑定方式,但我认为该Maybe类型实际上被用于编码de Bruijn索引.

基本思想是对绑定变量的引用存储为一个数字,指定要到达相关绑定器的周围绑定器的数量.因此,例如0表示最接近的周围粘合剂,1表示下一个最接近的粘合剂,依此类推.

我认为这里发生的事情是Maybe用来计算粘合剂.因此Nothing等于0并且指的是最接近的活页夹,并且Just Nothing等于1并且指的是下一个最接近的,依此类推.

所以在你的例子中,V Nothing将参考Lit 1,而V (Just Nothing)将参考Lit 3.