Enum polytype::Type

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

Represents monotypes (fully instantiated, unquantified types).

The primary ways of creating a Type are with the tp! macro or with TypeSchema::instantiate.

Variants

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

Primitive or composite types (e.g. int, List(α), α → β)

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(Variable)

Type variables (e.g. α, β) identified by de Bruin indices.

Examples

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

With the macros:

// map: (α → β) → [α] → [β]
let t = tp!(@arrow[
    tp!(@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 arrow(alpha: Type, beta: Type) -> Type

Construct a function type (i.e. alpha → beta).

pub fn as_arrow(&self) -> Option<(&Type, &Type)>

If the type is an arrow, get its associated argument and return types.

pub fn args(&self) -> Option<VecDeque<&Type>>

If the type is an arrow, recursively get all curried function arguments.

pub fn returns(&self) -> Option<&Type>

If the type is an arrow, get its ultimate return type.

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

Applies the type in a Context.

This will substitute type variables for the values associated with them by 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 generalize(&self, ctx: &Context) -> TypeSchema

Generalizes the type by binding free variables in a TypeSchema.

Examples

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

let mut ctx = Context::default();
ctx.extend(0, tp!(int));
let t_gen = t.apply(&ctx).generalize(&ctx);

assert_eq!(format!("{}", t_gen), "∀t1. int → t1");

pub fn free_vars(&self, ctx: &Context) -> Vec<Variable>

Compute all the free variables in a type.

Examples

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

let mut ctx = Context::default();
ctx.extend(0, tp!(int));
let fvs_computed = t.free_vars(&ctx);
let fvs_expected = vec![1];

assert_eq!(fvs_computed, fvs_expected);

pub fn substitute(&self, substitution: &HashMap<Variable, Type>) -> Type

Perform a substitution. This is analogous to apply.

Examples

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

let mut substitution = HashMap::new();
substitution.insert(0, tp!(int));
substitution.insert(1, tp!(bool));
let t = t.substitute(&substitution);

assert_eq!(format!("{}", t), "int → bool");

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 = tp!(@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<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.