Как выражения позволяют работать в AST?

Question

Рассматривать:

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

Let Конструктор позволяет мне связать выражение (первый аргумент), чтобы ссылаться на него во втором (V Nothing относится к этому).

Если я сделаю что-то вроде

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

который Lit делает Var Nothing Ссылаться на? Кроме того, я хотел бы обобщить это для нескольких привязок одновременно, и я понятия не имею, как это сделать. Я следовал за некоторыми примерами из превосходного пакета Эдварда Кметта, но теперь я и растерян, и потерян.

Answer 1

Я предполагаю немного, потому что я не видел этот стиль связывания раньше, но я думаю, что Maybe Тип эффективно используется для кодирования индексов де Брейна.

Основная идея заключается в том, что ссылки на связанные переменные хранятся в виде числа, определяющего количество окружающих связующих, которые необходимо пройти, чтобы достичь соответствующего связующего. Так, например, 0 будет относиться к ближайшему окружающему связующему, 1 - к следующему ближайшему, и так далее.

Я думаю, что здесь происходит, что Maybe вместо этого используется для подсчета связующих. Так Nothing эквивалентно 0 и относится к ближайшему связующему, и Just Nothing эквивалентно 1 и относится к следующему ближайшему, и так далее.

Так что в вашем примере V Nothing будет относиться к Lit 1, в то время как V (Just Nothing) будет относиться к Lit 3,