Haskell recursive problem, tiny parser. Check variables

Question

I'm still working on a tiny parser for a tiny language defined in a task at school. The parser that generates an AST(Abstract syntax tree) is working. What I want is to check the defined variables, they must be bounded by the let expression. First the method that is defined in the task(suggestion, not needed):

checkVars :: Expr -> Char 

data Expr =  Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr Expr Expr
    deriving(Eq, Show)

A valid sentence would be "let X be 5 in *(2,X)". X would normally be a Var and 5 is normally an int. And the last can be any part of the dataExpr type. Main point: X is used somewhere in the last expression. The datatype for let is:

Let Expr Expr Expr

Link to the other questions I've asked about this task here just FYI; First question Second question

As you see the datatype to the checkVars is Expr, so here is an example of what I would feed to that function:

parseProg "let X be 4 in let Y be *(2 , X) in let Z be +(Y , X) in
+(+(X , Y) , Z)"
Let (Var 'X') (Tall 4) (Let (Var 'Y') (Mult (Tall 2) (Var 'X')) (Let
(Var 'Z') (Sum (Var 'Y') (Var 'X')) (Sum (Sum (Var 'X') (Var 'Y')) (Var
'Z'))))
Just 24

This is an all-inclusive example, the top part is the string/program being parsed. The second part, starting at line 3 (Let) is the AST, input for the checkVars function. And the bottom part "Just 24" is the evaluation. Which I will be back here for more help for. Note: The point is to spit out the first unbound variable found as an error, and ' ' if everything is fine. Obviously if you want to do this another way you can.

THANK YOU for any input at all. :)

Answer 1

I would actually try to evaluate the AST. Start by processing (and thus removing) all the Lets. Now, try to evaluate the resulting AST. If you run across a Var then there is an unbound variable.

Answer 2

Here's something to think about:

The first field of your Let constructor is an Expr. But can it actually hold anything else than Vars? If not, you should reflect this by making that field's type, say, String and adapting the parser correspondingly. This will make your task a lot easier.

The standard trick to evaluating an expression with let-bindings (which you are doing) is to write a function

type Env = [(String, Int)]
eval :: Expr -> Env -> Int

Note the extra argument for the environment. The environment keeps track of what variables are bound at any given moment to what values. Its position in the type means that you get to decide its value every time you call eval on child expressions. This is crucial! It also means you can have locally declared variables: binding a variable has no effect on its context, only on subexpressions.

Here are the special cases:

• In a Var, you want to lookup the variable name in the environment and return the value that is bound to it. (Use the standard Prelude function lookup.)
• In a Let, you want to add an extra (varname, value) to the front of the environment list before passing it on to the child expression.

I've left out some details, but this should be enough to get you going a long way. If you get stuck, ask another question. :-)

Oh, and I see you want to return a Maybe value to indicate failure. I suggest you first try without and use error to indicate unbound variables. When you have that version of eval working, adapt it to return Maybe values. The reason for this is that working with Maybe values makes the evaluation quite a bit more complicated.