Difficulty: ***
This was a highly ambitious test, but arguably the most rewarding, because the students’ solutions were impressive. Most of them were able to complete the monomorphic part of the algorithm before either getting stuck or running out of time implementing unification. Around 10% of the class had a good stab at Part IV with three of the 139 students who sat the test scoring maximum marks. The average mark was around 74%.
Remark: the solution is arguably more elegant when type substitutions are represented as functions, whereupon the composition of substitutions can be implemented using built-in function composition (.). I decided to stick with substitution lists instead, as the idea of substitutions as functions would have been unfamiliar.
The test appears here almost exactly as it was originally set. Nobody left early!
Specification
Template File
More Information
The Wikipedia article on type inference provides a useful digest on Hindley/Milner/Damas type inference and Algorithm W. An implementation of Algorithm W in Haskell can be found in the article Algorithm W Step by Step. I recently came across another Haskell implementation which turned out to be very close to the one developed for this test, but I cannot locate the source. If anyone can point me to that I will update this page.