Sunday July 10th 2016

Edition 005

Type inference and automatic generalization

by Alex Casquete

http://casquete.es/

Type inference is one of the features of F# that becomes newest programmer’s favorite. In practice (and very briefly), it forces us to write less type annotations. For instance, with the following code:

let x = 42
let truth = true

The compiler infers that ‘x’ is an integer and ‘truth’ a Boolean. In that case, the type inference algorithm determines the type from values located on the right side. But the algorithm does not stop here, it can infer the type of arguments and return values of a function from the function body. In this example:

let isTheTruth n = 
    if n > 42 then true 
    else false

The argument ‘n’ is being used in a comparison with an integer and the function returns Boolean values, therefore, the compiler can easily infer that the function accepts an integer and returns a Boolean. But now let’s look at another piece of code:

let add p q = p + q

In this case the compiler infers that the function accepts and returns an integer. What is the reason for this? Basically, F# compiler, in absence of any other information, infers an integer as the type of arithmetic expressions. What is key in the above sentence is “any other information” because if, for instance, we have the function declaration and we make use of it, as follows:

let add p q = p + q
let result = add 2.0 40.0

The signature of the ‘add’ function changes to ‘float -> float’ because this time the compiler infers the type from the first made use of the function. The question in this situation could be then: how can I create a function that can work with integers, floats, or longs?
We can use the ‘inline’ keyword to define an inline function where the code is inlined at the call site during compilation.

let inline sum x y = x + y

In this situation, the type of arguments of ‘sum’ function are statically resolved and the signature of the function becomes this:

val inline sum :
  x: ^a -> y: ^b ->  ^c
    when ( ^a or  ^b) : (static member ( + ) :  ^a *  ^b ->  ^c)

We see that the type of the parameters is preceded by a caret (^) indicating a type that is replaced with the actual type at compile time instead of at runtime. The ‘when’ clause specifies constraints indicating that the type parameter must provide certain methods that can be called from the body of the function. In this case the type must provide the sum operator.
When the function does not depend on the type of a parameter, the inference algorithm tends to consider a parameter as a generic. This is what is called automatic generalization. For instance:

let compare p q = 
    if p < q then -1
    elif p > q then 1
    else 0

In this case, the signature of this function is:

val compare : p:'a -> q:'a -> int when 'a : comparison

That indicates that this is a function that takes two arguments with the same type and returns a value of that same type and also it must support comparison.
In many situations, however, the compiler is unable to infer the type. For example, the following code returns an error because the compiler is unable to determinate the type.

List.sortBy (fun x -> x.Length) ["three"; "two"; "one"] 

But if we rewrite the code like this:

["three"; "two"; "one"] |> List.sortBy (fun x -> x.Length)

Now the compiler is aware of types and can process them before evaluating the right part of the operator. And so we avoid having to use annotation types that is what we should always try to achieve with functional languages like F#.

Conclusion

Type inference is a powerful feature that F# provides to helps us to write less type annotations in many contexts like function arguments, return types, generic types, etc. It is important to know how the inference algorithm works to determine the type of a value or function: how the functions interact and are used, what kind of constraints are applied to a type and if not, how and when generalization to generics takes place.

Would you like to learn more?? Check out all F# courses here!

Share This Article:

Inferencia de tipos y la generalización automática

Alex Casquete

http://casquete.es/

Una de las características con la que cualquier programador queda atrapado al entrar en contacto por primera vez con F# es con la inferencia de tipos. Por ejemplo, a partir del siguiente código:

let x = 42
let truth = true

El compilador infiere que ‘x’ es de tipo entero y ‘truth’ de tipo booleano. En este caso, el algoritmo de inferencia de tipos determina el tipo a partir de los valores situados en el lado derecho. Pero el algoritmo no se queda aquí, puede inferir el tipo de los parámetros y de los valores devueltos de una función a partir del cuerpo de la función. En este ejemplo:

let isTheTruth n = 
    if n > 42 then true 
    else false

El argumento ‘n’ se está utilizando en una comparación con un entero y los valores devueltos son booleanos, por lo tanto, el compilador puede inferir fácilmente que la función acepta un entero y devuelve un booleano. Pero ahora veamos este otro ejemplo:

let add p q = p + q

En este caso el compilador infiere que la función acepta y devuelve un entero. ¿A qué es debido esto? Pues básicamente porque el compilador de F#, en ausencia de cualquier otra información, infiere un entero como el tipo de las expresiones aritméticas. Lo importante en la anterior afirmación es “cualquier otra información”, ya que si, por ejemplo, declaramos la función y hacemos uso de ella de la siguiente forma:

let add p q = p + q
let result = add 2.0 40.0

La firma de la función ‘add’ cambia a ‘float -> float’ ya que en esta ocasión el compilador infiere el tipo a partir del primer uso que se hace de la función. La pregunta en esta situación podría ser entonces: ¿cómo se puede hacer que una función pueda trabajar con enteros, floats o longs?
Podemos hacer uso del modificador inline para definir una función en línea, con las que las llamadas a estas funciones se reemplazan por el cuerpo de las funciones durante la compilación.

let inline sum x y = x + y

En este caso, los parámetros de la función ‘sum’ pasan a ser de tipo que se resuelven estáticamente y la firma de la función pasa a ser esta:

val inline sum :
  x: ^a -> y: ^b ->  ^c
    when ( ^a or  ^b) : (static member ( + ) :  ^a *  ^b ->  ^c)

Vemos que el tipo de los parámetros están precedidos por el acento circunflejo (^) que indican un tipo que será reemplazado por el tipo de verdad en tiempo de compilación en lugar de en ejecución. La cláusula ‘when’ especifica las restricciones que indican que el tipo del parámetro debe proveer ciertos métodos que pueden ser llamados desde el cuerpo de la función. En este caso, el tipo necesita proveer el operador suma.

Cuando la función no depende del tipo de un parámetro, el algoritmo de inferencia tiende a considerar un parámetro como genérico. Esto es lo que se llama generalización automática. Si tomamos el siguiente ejemplo:

let compare p q = 
    if p < q then -1
    elif p > q then 1
    else 0

La firma de esta función es:

val compare : p:'a -> q:'a -> int when 'a : comparison

Que nos indica que se trata de una función que toma dos argumentos del mismo tipo y devuelve un valor de ese mismo tipo y además debe soportar comparación.
En muchas situaciones, sin embargo, el compilador no es capaz de inferir el tipo. Por ejemplo, el siguiente código devuelve un error porque el compilador es incapaz de determinar el tipo.

List.sortBy (fun x -> x.Length) ["three"; "two"; "one"] 

Pero si reescribimos el código de esta forma:

["three"; "two"; "one"] |> List.sortBy (fun x -> x.Length)

El compilador es consciente de los tipos y puede procesar los tipos antes de evaluar la parte de la derecha del operador. Y de esta forma nos evitamos el tener que utilizar la anotación de tipos que es lo que deberíamos intentar siempre con lenguajes funcionales como F#.

Conclusión

La inferencia de tipos es una poderosa característica que nos proporciona F# para ayudarnos a escribir menos anotaciones de tipo en multitud de contextos como argumentos de funciones, tipos de retorno, tipos genéricos, etc.). Es importante conocer cómo funciona el algoritmo de inferencia para determinar el tipo de un valor o una función: cómo interactúan las funciones y cómo son usadas, que tipo de restricciones se aplican a los tipos y en el caso de que no haya, cómo y cuándo la generalización tiene lugar.

Would you like to learn more?? Check out all F# courses here!

Share This Article:

The F# Gazette

Relax and enjoy a curated selection of the best F# content straight to your inbox.

Including:
  • F# news round-up
  • Interviews with industry professionals
  • Guest articles from F# experts
  • Latest F# jobs
  • F# tools, tips, tutorials and more.