Now we've got our models, parser and helper functions we can quickly complete implementing algorithm M. We quickly implement the various cases for the different expressions, and then try out algorithm M on a load of different example cases. Having also completed algorithm W, we take a look at their internals to compare how they operate and why they throw different kinds of type errors.
Code on GitHub: https://github.com/domdomegg/hindley-milner-typescript-minimal
Paper in the video:
Lee, O., & Yi, K. (1998). Proofs about a folklore let-polymorphic type inference algorithm. ACM Transactions on Programming Languages and Systems (TOPLAS), 20(4), 707-723.
https://doi.org/10.1145/291891.291892
00:00 What have we done so far?
00:28 Algorithm M function signature
01:57 Variable expressions
02:54 Abstraction expressions
05:50 Application expressions
07:12 Let-in expressions
08:47 Calling the algorithm
11:04 Trying it out
11:37 Top-down vs bottom-up
16:01 Recap
