polytype

A Hindley-Milner polymorphic typing system. Implements type inference via unification.

Usage

toml [dependencies] polytype = "3.0"

Provided by polytype are the Type and Type enums, the Context struct, and the macros tp!, arrow!, and ptp!, which help to concisely create types and type schemas.

Unification:

```rust let mut ctx = Context::default();

// t1: list(int → α) ; t2: list(β → bool) let t1 = tp!(list(arrow![tp!(int), tp!(0)])); let t2 = tp!(list(arrow![tp!(1), tp!(bool)])); ctx.unify(&t1, &t2).expect("unifies");

let t1 = t1.apply(&ctx); let t2 = t2.apply(&ctx); assert_eq!(t1, t2); // list(int → bool) ```

Apply a type context:

```rust let mut ctx = Context::default(); // assign t0 to int ctx.unify(&tp!(0), &tp!(int)).expect("unifies");

let t = tp!(list(tp!(0))); asserteq!(format!("{}", &t), "list(t0)"); let t = t.apply(&ctx); asserteq!(format!("{}", &t), "list(int)"); ```

Instantiate a TypeSchema:

```rust let mut ctx = Context::default();

// ∀α. list(α) let schema = ptp!(3; tp!(list(tp!(3))));

// They instantiate to new fresh type variables let t1 = schema.instantiate(&mut ctx); let t2 = schema.instantiate(&mut ctx); asserteq!(format!("{}", &t1), "list(t0)"); asserteq!(format!("{}", &t2), "list(t1)"); ```

See the documentation for more details.