Enum polytype::Type

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

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

Variants

Arrow(Box<Arrow>)

For functions α → β.

If a function has many arguments, use currying.

Examples

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

With the macros:

let t = arrow![tp!(0), tp!(1), tp!(int), tp!(bool)];
assert_eq!(format!("{}", &t), "t0 → t1 → int → bool");

Constructed(&'static str, Vec<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![tint]);
assert_eq!(format!("{}", &tlist_of_ints), "list(int)");

With the macros:

let t = tp!(list(tp!(int)));
assert_eq!(format!("{}", &t), "list(int)");

Variable(u32)

For type variables.

Examples

// any function: α → β
let t = arrow![Type::Variable(0), Type::Variable(1)];
assert_eq!(format!("{}", &t), "t0 → t1");

With the macros:

// map: (α → β) → [α] → [β]
let t = arrow![
    arrow![tp!(0), tp!(1)],
    tp!(list(tp!(0))),
    tp!(list(tp!(1))),
];
assert_eq!(format!("{}", &t), "(t0 → t1) → list(t0) → list(t1)");

Methods

impl Type

pub fn is_polymorphic(&self) -> bool

Whether a type has any type variables.

pub 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(&tp!(0), &tp!(int)).expect("unifies");

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

pub 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 = tp!(list(tp!(3)));
let t2 = tp!(list(tp!(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)");

pub 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 = tp!(list(tp!(3)));
let t2 = tp!(list(tp!(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)");

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

Canonicalizes the type by instantiating in an empty context.

Replaces type variables according to bindings.

pub fn parse(s: &str) -> Result<Type, ()>

Parse a type from a string. This round-trips with Display. This is a leaky operation and should be avoided wherever possible: names of constructed types will remain until program termination.

Examples

let t_par = Type::parse("int -> hashmap(str, list(bool))").expect("valid type");
let t_lit = arrow![tp!(int), tp!(hashmap(tp!(str), tp!(list(tp!(bool)))))];
assert_eq!(t_par, t_lit);

let s = "(t1 → t0 → t1) → t1 → list(t0) → t1";
let t = Type::parse(s).expect("valid type");
let round_trip = format!("{}", &t);
assert_eq!(s, round_trip);

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 Hash for Type

fn hash<__H: Hasher>(&self, __arg_0: &mut __H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

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 Eq for Type

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.

impl From<VecDeque<Type>> for Type

fn from(tps: VecDeque<Type>) -> Type

Performs the conversion.

impl From<Vec<Type>> for Type

fn from(tps: Vec<Type>) -> Type

Performs the conversion.