Enum polytype::Type

pub enum Type {
    Arrow(Arrow),
    Constructed(&'static str, Vec<Box<Type>>),
    Variable(u32),
}

Represents a type in the Hindley-Milner polymorphic typing system.

Variants

Arrow(Arrow)

For functions α → β.

If a function has many arguments, use currying.

Examples

let t = Type::Arrow(Arrow::new(Type::Variable(0), Type::Variable(1)));
assert_eq!(format!("{}", &t),
           "t0 → t1");

With arrow! macro:

let t = arrow![
    Type::Variable(0),
    Type::Variable(1),
    Type::Variable(2),
    Type::Variable(3),
];
assert_eq!(format!("{}", &t),
           "t0 → t1 → t2 → t3");

Constructed(&'static str, Vec<Box<Type>>)

For primitive or composite types.

Examples

Primitives have no associated types:

let tint = Type::Constructed("int", vec![]);
assert_eq!(format!("{}", &tint), "int")

Composites have associated types:

let tint = Type::Constructed("int", vec![]);
let tlist_of_ints = Type::Constructed("list", vec![Box::new(tint)]);
assert_eq!(format!("{}", &tlist_of_ints),
           "list(int)");

Composites may often warrant writing shorthand with a dedicated function:

fn tlist(tp: Type) -> Type {
    Type::Constructed("list", vec![Box::new(tp)])
}

let tint = Type::Constructed("int", vec![]);
let tlist_of_ints = tlist(tint);
assert_eq!(format!("{}", &tlist_of_ints),
           "list(int)");

Variable(u32)

For type variables.

Examples

// map: (α → β) → [α] → [β]
let t0 = Type::Variable(0);
let t1 = Type::Variable(1);
fn tlist(tp: Type) -> Type {
    Type::Constructed("list", vec![Box::new(tp)])
}

// the map type
let t = arrow![
    arrow![t0.clone(), t1.clone()],
    tlist(t0.clone()),
    tlist(t1.clone()),
];
assert_eq!(format!("{}", &t),
           "(t0 → t1) → list(t0) → list(t1)");

Methods

impl Type

fn is_polymorphic(&self) -> bool

Whether a type has any type variables.

fn apply(&self, ctx: &Context) -> Type

Applies the type in a context.

This will replace any type variables that have substitutions defined in the context.

Examples

let mut ctx = Context::default();
ctx.unify(&Type::Variable(0), &Type::Constructed("int", vec![])).expect("unifies");

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

fn instantiate_indep(&self, ctx: &mut Context) -> Type

Independently instantiates a type in the context.

All type variables will be replaced with new type variables that the context has not seen. Equivalent to calling Type::instantiate with an empty map.

Examples

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.instantiate_indep(&mut ctx);
let t2 = t2.instantiate_indep(&mut ctx);
assert_eq!(format!("{}", &t1), "list(t0)");
assert_eq!(format!("{}", &t2), "list(t1)");

fn instantiate(
    &self,
    ctx: &mut Context,
    bindings: &mut HashMap<u32, Type>
) -> Type

Dependently instantiates a type in the context.

All type variables will be replaced with new type variables that the context has not seen, unless specified by bindings. Mutates bindings for use with other instantiations, so their type variables are consistent with one another.

Examples

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);
assert_eq!(format!("{}", &t1), "list(t0)");
assert_eq!(format!("{}", &t2), "list(t0)");

fn canonical(&self, bindings: &mut HashMap<u32, Type>) -> Type

Canonicalizes the type by instantiating in an empty context.

Replaces type variables according to bindings.

Trait Implementations

impl Debug for Type

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl Clone for Type

fn clone(&self) -> Type

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl PartialEq for Type

fn eq(&self, __arg_0: &Type) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, __arg_0: &Type) -> bool

This method tests for !=.

impl Display for Type

fn fmt(&self, f: &mut Formatter) -> Result<(), Error>

Formats the value using the given formatter.

impl From<Arrow> for Type

fn from(arrow: Arrow) -> Type

Performs the conversion.