haskell - Let式はASTでどのように機能しますか?

Question

検討：

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

コンストラクターを使用Letすると、式 (最初の引数) をバインドして、2 番目の ( V Nothingrefer to it) で参照することができます。

私が何かをするなら

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

LitはどれをVar Nothing指しますか？さらに、それを一度に複数のバインディングに一般化したいのですが、その方法がわかりません。私は優れた Edward Kmett製本パッケージのいくつかの例に従いましたが、今では混乱して途方に暮れています。

score 9 · Accepted Answer

このスタイルのバインディングを前に見たことがないので、少し推測していますが、この型はde Bruijn インデックスMaybeをエンコードするために効果的に使用されていると思います。

基本的な考え方は、バインドされた変数への参照は、関連するバインダーに到達するために通過する周囲のバインダーの数を指定する数値として格納されるということです。たとえば、0 は最も近い周囲のバインダーを参照し、1 は次に近いバインダーを参照します。

ここで起こっているのは、Maybe代わりにバインダーをカウントするために使用されていることだと思います。SoNothingは 0 に相当し、最も近いバインダーをJust Nothing参照し、1 に相当し、次に近いバインダーを参照します。

したがって、あなたの例では、V Nothingはを参照しますがLit 1、V (Just Nothing)はを参照しLit 3ます。

1 に答える 1