Clojure Data Structures and Algorithms Cookbook

Designing a type inferencer

If you've ever worked with dynamically typed languages, you may have had a taste of what type inferencing is. During runtime or compile time, your program's variables and expression types are deduced to a starting set of a given rules that describe some basic type associations. Generally, this field comes along with a wide range of academic theory and its inherent mechanics can reach a high level of complexity when advanced language constructions, such as lambda expressions or polymorphic structures, come into play.

As far as our recipe is concerned, we are going to implement a subset of an algorithm known as Hindley-Milner (or Damas-Milner) to keep things simple. In Hindley-Milner, we maintain an environment of known ...