Loading...
Type inference in Haskell
Type inference vs type-checking
Standard type checking
int
f
(
int
x)
{
return
x * x }
int
g
(
int
x)
{
return
x * f(x) }
Examine body of each function
Use declared types to check agreement
Type inference
int
f
(
int
x)
{
return
x * x }
int
g
(
int
x)
{
return
x * f(x) }
Examine code without type information
Infer the most general types that could have been declared
Haskell examples
https://repl.it/@blackdahila/InferenceExamples
Type inference algorithm
Assign a type or type variable to the expression and each subexpression.
Generate a set of constraints on types, using the parse tree of the expression.
Solve these constraints by unification.
Example 1
1. Assign a type variable to the expression and each subexpression
2. Generate a set of constraints on types, using the parse tree of the expression
3. Solve the generated constraints using unification
Step 1
Step 2
Step 3
Example 2: Polymorphic functions
1. Assign a type variable to the expression and each subexpression
2. Generate a set of constraints on types, using the parse tree of the expression
3. Solve the generated constraints using unification
Step 1
Step 2
Please turn on JavaScript to use Paper in all of its awesomeness. ^_^
Type inference vs type-checking
int f(int x) { return x * x }int g(int x) { return x * f(x) }intf(intx) { return x * x }intg(intx) { return x * f(x) }Haskell examples
Type inference algorithm
Example 1
1. Assign a type variable to the expression and each subexpression
2. Generate a set of constraints on types, using the parse tree of the expression
3. Solve the generated constraints using unification
Example 2: Polymorphic functions
1. Assign a type variable to the expression and each subexpression
2. Generate a set of constraints on types, using the parse tree of the expression
3. Solve the generated constraints using unification