polytype

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

Usage

toml [dependencies] polytype = "1.0"

Provided by polytype are the Type enum and the Context struct.

Unification:

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

let tbool = Type::Constructed("bool", vec![]); let tint = Type::Constructed("int", vec![]); fn tlist(tp: Type) -> Type { Type::Constructed("list", vec![Box::new(tp)]) }

// t1: list(int → α) ; t2: list(β → bool) let t1 = tlist(Type::Arrow(Arrow::new(tint, Type::Variable(0)))); let t2 = tlist(Type::Arrow(Arrow::new(Type::Variable(1), tbool))); 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(&Type::Variable(0), &Type::Constructed("int", vec![])).expect("unifies");

let t = Type::Constructed("list", vec![Box::new(Type::Variable(0))]); asserteq!(format!("{}", &t), "list(t0)"); let t = t.apply(&ctx); asserteq!(format!("{}", &t), "list(int)"); ```

Independent instantiation:

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

let t1 = Type::Constructed("list", vec![Box::new(Type::Variable(3))]); let t2 = Type::Constructed("list", vec![Box::new(Type::Variable(3))]);

let t1 = t1.instantiateindep(&mut ctx); let t2 = t2.instantiateindep(&mut ctx); asserteq!(format!("{}", &t1), "list(t0)"); asserteq!(format!("{}", &t2), "list(t1)"); ```

Dependent instantiation:

```rust use std::collections::HashMap;

let mut ctx = Context::default();

let t1 = Type::Constructed("list", vec![Box::new(Type::Variable(3))]); let t2 = Type::Constructed("list", vec![Box::new(Type::Variable(3))]);

let mut bindings = HashMap::new(); let t1 = t1.instantiate(&mut ctx, &mut bindings); let t2 = t2.instantiate(&mut ctx, &mut bindings); asserteq!(format!("{}", &t1), "list(t0)"); asserteq!(format!("{}", &t2), "list(t0)"); ```

See the documentation for more details.