Inductive data type

Learning
1

Hello,
I am working on the topic of inductive data type and I don’t quite understand the following type:
type environment = (string * value) list
I am using this to define my new expression evaluation. For instance, I need to evaluate:

Add (Int 4, Mul (Int 3, Id "x"))

where

type value 
= Int of int | Bool of bool

type expr 
= Val of value

| Add of expr * expr
| Sub of expr * expr
| Mul of expr * expr
| Div of expr * expr 
| Lt of expr * expr
| Eq of expr * expr
| And of expr * expr
| Not of expr
| Let of string * expr * expr
| Id of string

what does this look like?
How can I understand this new type environment?

I am guessing in my above expression:

Add (Int 4, Mul (Int 3, Id "x"))

I need to know what “x” is, so I need a sorta environment to convert “x” to a computational or operational variable that can be evaluated through an evaluation.
But I am not sure how to correctly understand type environment.
Please help.
Thank you!

2

Your expression contains Id elements. To evaluate an expression to a value, you need to know the value for each Id. This is provided by the environment: it should contain a value for each Id element that you find. You need a function like lookup

val lookup: string -> environment -> value
val eval: environment -> expr -> value

such that you can call lookup "x" env to get back Int(42) when you implement eval. In particular:

eval [("x", Int(42))] (Id "x") => Int(42)
1 Like