How do Let expressions work in AST?

Question

Consider:

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

The Let constructor allows me to bind an expression (the first arg) to refer to it in the second ( V Nothing refers to it).

If I'm something like

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

to which Lit refers to Var Nothing ? Also, Id would like to generalize this to multiple bindings at once, and I don't know how to do this. I gave some examples from the excellent Edward Kmett bound package, but now Im both confused and lost.

Answer 1

I have a little guess, because I have not seen this binding style before, but I think that Maybe type is used effectively for coding de Bruijn Indexes .

The basic idea is that references to related variables are stored as a number that defines the number of surrounding binders to go through the corresponding binder. So, for example, 0 will refer to the nearest neighboring binder, 1 to the nearest nearest, etc.

I think what happens here is that Maybe used to count binders. So, Nothing equivalent to 0 and refers to the nearest binder, and Just Nothing equivalent to 1 and refers to the nearest nearest, etc.

So, in your example, V Nothing will refer to Lit 1 , while V (Just Nothing) will refer to Lit 3 .