7.9 Type Inference

Explicit type declarations of values and variables help inform a static type system.
For example, consider these explicit declarations of types for entities in ML:

Types for values, variables, function parameters, and return types are similarly declared in Haskell:

In some languages with first-class functions, especially statically typed languages, functions have types. Instead of ascribing a type to each individual parameter and the return type of a function, we can declare the type of the entire function. In ML, a programmer can explicitly declare the type of an entire anonymous function and then bind the function definition to an identifier:

In Haskell, a programmer can explicitly declare the type of both a non-anonymous and an anonymous function:

Explicitly declaring types requires effort on the part of the programmer and can be perceived as requiring more effort than necessary to justify the benefits of a static type system. Type inference is a concept of programming languages that represents a compromise and attempts to provide the best of both worlds. Type inference refers to the automatic deduction of the type of a value or variable without an explicit type declaration. ML and Haskell use type inference, so the programmer is not required to declare the type of any variable unless necessary (e.g., in cases where it is impossible for type inference to deduce a type). Both languages include a built-in type inference engine to deduce the type of a value based on context. Thus, ML and Haskell use type inference to relieve the programmer of the burden of associating a type with every name in a program. However, an explicit type declaration is required when it is impossible for the inference algorithm to deduce a type. ML introduced the idea of type inference in programming languages in the 1970s.

Both ML and Haskell use the Hindley–Milner algorithm for type inference. While the details of this algorithm are complex and beyond the scope of this text, we will make some cursory remarks on its use. Understanding the fundamentals of how these languages deduce types helps the programmer know when explicit type declarations are required and when they can be omitted. Though not always necessary, in ML and Haskell, a programmer can associate a type with (1) values, (2) variables, (3) function parameters, and (4) return types. The main idea in type inference is this: Since all operands to a function or operator must be of the required type, and since values of differing numeric types cannot be mixed as operands to arithmetic operators, once we know the type of one or more values in an expression (because, for example, it was explicitly declared to be of that type) by transitive inference we can progressively determine the type of each other value. In essence, knowledge of the type of a value (e.g., a parameter or return value) can be leveraged as context to determine the types of other entities in the same expression. For instance, in ML:

Declaring the parameter x to be of type real is enough for ML to deduce the type of the function add’ as fn : real * real -> real. Since the first operand to the + operator is a value of type real, the second operand must also be of type real because the types of the two operands must be the same. In turn, the return type is a value of type real because the sum of two values of type real is a value of type real. A similar line of reasoning is used in ML to deduce that the type of add" and the type of . The Haskell analogs of these examples follow:

In these ML and Haskell examples, where partial or complete type information is provided, the explicitly declared type is not always the same as the type that would have been inferred. For instance, in ML:

In Haskell, for these examples, the inferred type is never the same as the declared type:

In general, we only explicitly declare the type of an entity in ML or Haskell when the inferred type is not the intended type. If the inferred type is the same as the intended type, explicitly declaring the type is redundant. For instance:

With a named function, we must provide the type inference engine in ML with partial information from which to deduce the intended type of the function by associating a type with a parameter, variable, and/or return value. Sometimes no explicit type declaration (of a parameter or return value) is required, and the context of the expression is sufficient for ML or Haskell to infer a particular intended function type. For instance, consider the following ML function:

Here, the type of f is inferred: Adding 0.0 to a means that a must be of type real (because the numeric type of each operand must match), so b must be of type real. Consider another example where information other than an explicitly declared type is used as a basis for type inference:

Here, the 0 returned in the first case of the sum function causes ML to infer the type int list -> int for the function sum because 0 is an integer and a function can only return a value of one type.

In ML, when there is no way to determine the type of an operand of an operator, such as +, the type of the operand is inferred to be the default type for that operator. The default numeric type of any operand for arithmetic operators (e.g., +, -, *, and <) and numeric values is int in ML. For instance, consider the following ML functions and their inferred types:

In an if ...then ...else expression, the conditional expression as well as the expressions following the lexemes if and else must return a value of the same type:

Lastly, remember that ML supports polymorphic types, so the inferred type of some functions includes type variables:

In Haskell every expression must have a type, which is calculated prior to evaluating the expression by a process called type inference. The key to this process is a typing rule for function application, which states that if f is a function that maps arguments of type A to results of type B, and e is an expression type A, then the application f e has type B:

For example, the typing ¬ False :: Bool can be inferred from this rule using the fact that not::Bool→Bool and False::Bool. (Hutton 2007, pp. 17–18)

Recall that it is not possible in ML and Haskell to deviate from the types required by operators and functions. However, type inference offers some relief from having to declare a type for all entities. Notably, it supports static typing without explicit type declarations. If you know the intended type of a user-defined function, but are not sure which type will be inferred for it, you may explicitly declare the type of the entire function (rather than explicitly declaring types of selective parameters or values, or the return type, to assist the inference engine in deducing the intended type), if possible, rather than risk that the inferred type is not the intended type. Conversely, if it is clear that the type that will be inferred is the same as the intended type, there is no need to explicitly declare the type of a user-defined function. Let the inference engine do that work for you.

Strong typing provides safety, but requires a type to be associated with every name. The use of type inference in a statically typed language obviates the need to associate a type with each identifier:

Static, Safe Type System + Type Inference Obviates the Need to Declare Types

Static, Safe Type System + Type Inference ⇝ Reliability/Safety + Manifest Typing