Magic type inference of ML languages
How does type inference work in ML languages like standard-ML, OCAML, F#, Elm, Reason and even Haskell or to some extent Rust? Letās call it Magic. How does this kind of magic work?
We are going to take a look at the case of F# but once you learn this concept, you will understand how it works in all ML languages and even in Haskell, or potentially others.
I suggest to follow along and try things in your editor, so you just need a simple brew install dotnet on your mac, winget on windows or follow the guide for your OS. Then run on your cli:
dotnet --version
dotnet fsi // launches F# interactive
>let x = 5;; // type any F# followed by `;;` to execute
>#quit;; // exit fsi
To edit files, you can use VsCode+Ionide extension, Rider or VisualStudio. Just name a new file as .fsx
and you are ready to go, with alt/option + enter you can select and execute portions of code in the REPL.
Or if you feel lazy try it in your browser.
Variable binding š
The simplest case is for binding is 1 value, this is the kind of magic we all know already. The compiler in a similar fashion as what happens in other languages e.g., C# or typescript, will infer our type for us, in this case, int. No big surprises here.
let x = 5 // int
IDEs will show the type either above or next to the binding expression.
A function binding (wow moment starts!) āļø
This case is different from any other languages you know of most likely, but you have to think of it as working in a similar fashion as we have seen before, just stretching a bit your imagination.
let addEleven y = //1. int -> int
y + 11
let addString z = //2. string -> string
z + " world"
How does this work? In practice it can get complicated but I will try to make it simpler for me and for you. Letās analyse these 2 cases:
- The result is something that can be summed to an integer type, so
y
+int
=int
, the compiler will resolve the type ofy
to beint
. - The result has to be
string
, with a similar reasoning:z
+string
= string, hencez
must be astring
.
Think about this for a second. Have you seen this in other languages? Maybe yes, maybe no. Maybe you tried Elm or Reason languages, and thatās exactly how it works there as well.
My bet is that it might be something completely new to you. Types are inferred in a chain by the compiler using the ML inference algorithm, for which some smart guys like Milner won academic awards such as the Alan Turing award!
No need to write type annotations in signatures or anywhere! awesome! you can still do it if you feel like ofc, just a bit in the opposite way typescript works, below the proof!
Compare with TS
You can use these 2 online compilers to follow along:
On the other hand, F# seems to be smarter, as it can infer types using the ML inference algorithm!
This means that code looks as slim as JavaScript, but itās statically typed as C# or Java!
The compiler is in charge! š¤ āļø
When changing return values, your code magically ārefactors itselfā trying to infer the correct types or, eventually, fails the compilation!
let add5 x = // int -> int
x + 5
let someWrongFunction () = // compilation error!!!
add5 "hello"
let okAdditionFunction () = // OK! unit -> int
add5 100
A Function of functions! š
In this case, with a higher order function (a.k.a. function of functions) the compiler still infers correctly all values, based on which operator you used and applying the types in the function chain along with it. So, starting from left + 3, the return type must be an int
, everything on the left must also be an int
!
let someComplexFunction someFunction argument = // ('a -> int) -> 'a -> int
someFunction(argument) + 3
This means someFunction(argument)
must return an int
, but argument
can be a generic type āa
, we don't know yet what type it will be, so itās automatically generalized.
Generic Without T
No more hassle with <T> in our code, the compiler guesses it for us in most cases, and we can type only where we need to do so and itās not explicit for the compiler.
The first usage of this function in code will nail it šØ down its type! for example
let addOne x = x + 1 // int -> int
let z = someComplexFunction addOne 5 // 9: int
Feel free to play around in your favorite editor or online if you are lazy.
Compare and imagine
Compare this to a more complex scenario and imagine (or try it out)
How does refactoring look like in a language with explicit type signatures like C# or Typescript or Java for example, versus an ML language. Letās see how a simple add function compares to other languages, here is F#:
let addOne a = a + 1 // int -> int
let addOneShorter = (+1) // int -> int
Compare with Java/C#, we still need to specify signatures along the way
public int AddOne(int a) { // we must supply the signature types
return a + 1;
}
How does this code compare to a dynamic language like JavaScript or python? Here, life seems sweet as we donāt have type signatures!
def addOne(a) = ## shorter, but do we get any type check here? š
a + 1
JavaScript and Typescript, here it seems we can do both, but when adding types, we lose the succinct look of the language. See the section above to revisit this specific comparisonā¦
const addOneFirst = a => a + 1; // any -> any
const addOneSecond = (a: int) => a + 1; // int -> int
At a first glance it might look like F# is similar to JavaScript or python, but can you tell the differenceā
let addOne a = a + 1 // int -> int
Refactoring Code ā
Think of very long call chains and nested calls, is it easier to refactor in which language and why? In which language does it feel safer?
My take on refactoring is that itās usually easier to refactor in dynamic languages, but safer to refactor in static languages, with the cons of having to adjust all signatures and type annotations with some assistant tooling (like rider or ReSharper or IDE refactoring assistants).
In F# and ML languages in general itās both easy and safe to refactor, without the need of external tooling, as the type inference engine will walk through your code while changing it, and constantly give you compiler feedback if anything went wrong along the chain.
Boomer* sheet to compare types
I quickly sketched a table with subjective pros and cons in this language comparison table.
Legend: šgood, šmeh, šnah.
Donāt forget to give F# a try if you havenāt yet!