Enum polytype::Type

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

Represents monotypes (fully instantiated, unquantified types).

The primary ways to create a Type are with either the tp! macro or TypeScheme::instantiate. Type::arrow constructs function types (i.e. α → β), as does conversion (Type::from) with Vec and VecDeque for curried arrows.

Variants

Constructed(N, Vec<Type<N>>)

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

Examples

Primitives have no associated types:

let tint = Type::Constructed("int", vec![]);
assert_eq!(tint.to_string(), "int")

Composites have associated types:

let tint = Type::Constructed("int", vec![]);
let tlist_of_ints = Type::Constructed("list", vec![tint]);
assert_eq!(tlist_of_ints.to_string(), "list(int)");

With the macro:

let t = tp!(list(tp!(int)));
assert_eq!(t.to_string(), "list(int)");

Function types, or “arrows”, are constructed with either Type::arrow, two implementations of Type::from — one for Vec<Type> and one for VecDeque<Type> — or the macro:

let t = Type::arrow(tp!(int), tp!(bool));
assert_eq!(t.to_string(), "int → bool");

let t = Type::from(vec![tp!(int), tp!(int), tp!(bool)]);
assert_eq!(t.to_string(), "int → int → bool");

let t = tp!(@arrow[tp!(int), tp!(int), tp!(bool)]); // prefer this over Type::from
assert_eq!(t.to_string(), "int → int → bool");

Variable(Variable)

Type variables (e.g. α, β).

Examples

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

With the macro:

// map: (α → β) → [α] → [β]
let t = tp!(@arrow[
    tp!(@arrow[tp!(0), tp!(1)]),
    tp!(list(tp!(0))),
    tp!(list(tp!(1))),
]);
assert_eq!(t.to_string(), "(t0 → t1) → list(t0) → list(t1)");

Implementations

impl<N: Name> Type<N>

pub fn arrow(alpha: Type<N>, beta: Type<N>) -> Type<N>

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

Examples

let t = Type::arrow(tp!(int), tp!(bool));
assert_eq!(t.to_string(), "int → bool");

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

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

Examples

let t = tp!(@arrow[tp!(int), tp!(int), tp!(bool)]);
if let Some((left, right)) = t.as_arrow() {
    assert_eq!(left.to_string(), "int");
    assert_eq!(right.to_string(), "int → bool");
} else { unreachable!() }

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

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

Examples

let t = tp!(@arrow[tp!(int), tp!(int), tp!(bool)]);
if let Some(args) = t.args() {
    assert_eq!(args.len(), 2);
    assert_eq!(args[0].to_string(), "int");
    assert_eq!(args[1].to_string(), "int");
} else { unreachable!() }

pub fn args_destruct(self) -> Option<Vec<Type<N>>>

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

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

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

Examples

let t = tp!(@arrow[tp!(int), tp!(int), tp!(bool)]);
if let Some(ret) = t.returns() {
    assert_eq!(ret.to_string(), "bool");
} else { unreachable!() }

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

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!(t.to_string(), "list(t0)");
let t = t.apply(&ctx);
assert_eq!(t.to_string(), "list(int)");

pub fn apply_mut(&mut self, ctx: &Context<N>)

Like apply_compress, but works in-place.

pub fn generalize(&self, bound: &[Variable]) -> TypeScheme<N>

Generalizes the type by quantifying over free variables in a TypeScheme.

Variables specified by bound remain unquantified.

Examples

let t = tp!(@arrow[tp!(0), tp!(1)]);
assert_eq!(t.to_string(), "t0 → t1");

let mut ctx = Context::default();
ctx.extend(0, tp!(int));

let t_gen = t.apply(&ctx).generalize(&[]);
assert_eq!(t_gen.to_string(), "∀t1. int → t1");

let t_gen = t.apply(&ctx).generalize(&[1]);
assert_eq!(t_gen.to_string(), "int → t1");

pub fn vars(&self) -> Vec<Variable>

Compute all the variables present in a type.

Examples

let t = tp!(@arrow[tp!(0), tp!(1)]);
assert_eq!(t.to_string(), "t0 → t1");

let mut vars = t.vars();
vars.sort();
assert_eq!(vars, vec![0, 1]);

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

Perform a substitution. This is analogous to apply.

Examples

let t = tp!(@arrow[tp!(0), tp!(1)]);
assert_eq!(t.to_string(), "t0 → t1");

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

let t = t.substitute(&substitution);
assert_eq!(t.to_string(), "int → bool");

pub fn substitute_mut(&mut self, substitution: &HashMap<Variable, Type<N>>)

Like substitute, but works in-place.

Trait Implementations

impl<N: Clone + Name> Clone for Type<N>

fn clone(&self) -> Type<N>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N: Debug + Name> Debug for Type<N>

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

Formats the value using the given formatter.

impl<N: Name> Display for Type<N>

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

Formats the value using the given formatter.

impl<N: Name> From<Vec<Type<N>>> for Type<N>

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

Converts to this type from the input type.

impl<N: Name> From<VecDeque<Type<N>>> for Type<N>

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

Converts to this type from the input type.

impl<N: Name> FromStr for Type<N>

fn from_str(s: &str) -> Result<Type<N>, ParseError>

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 = "int -> hashmap(str, list(bool))".parse().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<&'static str> = s.parse().expect("valid type");
let round_trip = t.to_string();
assert_eq!(s, round_trip);

type Err = ParseError

The associated error which can be returned from parsing.

impl<N: Hash + Name> Hash for Type<N>

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

Feeds this value into the given Hasher.

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

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<N: PartialEq + Name> PartialEq for Type<N>

fn eq(&self, other: &Type<N>) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<N: Eq + Name> Eq for Type<N>

impl<N: Name> StructuralEq for Type<N>

impl<N: Name> StructuralPartialEq for Type<N>