We will use the following Haskell data types to represent Nano's types and poly$-$types. $($A "poly$-$type" is a polymorphic type, like the type of the identity function, $\backslash$x $->$ x: its type is forall a $.$ a $->$ a$.($Haskell also has polymorphic types, but you don't usually write the forall a $.$ part.$)$

data Type $=$ TInt $--$ Int $|$ TBool $--$ Bool $|$ Type :$=>$ Type $--$ function type: T$1->$ T$2|$ TVar TId $--$ type variable: a$,$ b$,$ c $|$ TList Type $--$ list type: $[$T$]$ data Poly $=$ Mono Type $--$ mono$-$type $|$ Forall TVar Poly $--$ polymorphic type

Above, TId is just a type alias for String, used to represent type variable names:

type TId $=$ String

For example, a Nano type Int $->$ Int is represented inside your type checker as:

TInt :$=>$ TInt

whereas a polymorphic Nano type forall a $.$ List a $->$ a is represented as:

Forall $"$a$"($Mono $($TList $($TVar $"$a$")$ :$=>$ TVar $"$a$"))$

$($or simply forall $"$a$"($list $"$a$"$ :$=>"$a$")$ using convenience functions forall and list, also defined in Types.hs$).$

Type Environments

A type environment is a dictionary that maps program variables to poly$-$types. As before, the dictionary is implemented as a list of pairs:

type TypeEnv $=[($Id$,$ Poly$)]$

For example, a type environment that maps the program variable x to the type Int, and maps the program variable f to the type Int $->$ Int, is represented as: