Algorithm W in TypeScript, for Hindley-Milner type inference

Now we've got our models, parser and helper functions we can quickly complete implementing algorithm W. We quickly implement the various cases for the different expressions, and then try out algorithm W on a load of different example cases.

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.

00:00 What have we done so far?
00:34 Algorithm W recap
01:09 Function signature
02:07 Variable expressions
03:56 Abstraction expressions
05:58 Application expressions
07:53 Let-in expressions
09:50 Testing: basics
11:24 Testing: contexts
14:29 Parser: adding parentheses
15:59 Testing: advanced expressions
16:20 Testing: let polymorphism
17:56 Testing: partial function application
19:31 What's next

[jakerunzer]

I've been trying to understand and implement type inference for a while. These videos have been super helpful and I can't thank you enough :D

[scythe]

I don't really want to calculate myself the time complexity of that thing.. is there a more precise measure than just the problem being DEXPTIME for ML languages ?

[guppiefang]

I'm trying to implement this now for my own language. One thing I'm wondering about is how these Hindley Milner monotype "type variables" map to "type variables" that you have in a generic function like you'd write in say Swift or Kotlin. You might declare such a function signature like `fun foo<T>(things: List<T>) -> Option<T>`. That example takes a list of anything and returns an optional of that same element type. When type checking the function body, it seems like `T` would be a type variable like described in these videos, but I guess the difference is that the type-checker wouldn't try to find out what T is, because the "generic" signature tells the type checker that unification doesn't need to resolve `T` to a concrete type function (Int, String, etc). Does that sound right?

By the way, are you working on this stuff in academia, or ...?? Just curious why you made the videos. Thanks again.