type_functions.rs

#![feature(optin_builtin_traits)]

use std::marker::PhantomData;

// Type functions in modern Rust:

// The signature of a type function is a trait.
// The trait's associated types correspond to the function's range.
// Its type parameters excluding the last parameter correspond to the function's
// domain.
// For a type function f: * -> *, the corresponding trait is

trait F_<X, IT> {
    type Type;
}
type F<X, IT> = <() as F_<X, IT>>::Type; // Purely convenience for calling F

// IT ("Inferred Type") is used by the implementation of F to constrain
// otherwise unconstrained type parameters, and to make the cases of F not
// conflict with each other.
// IT is a type that must be propagated to the IT parameter of any type
// function that uses F. A top level IT parameter is then inferred upon use of
// the type function as part of the invocation of a normal function.

// An example implementation of this function goes as follows:

#[allow(unused)]
struct F1; // Distinguishing type for the first case of F
#[allow(unused)]
struct F2; // For the second case

unsafe trait NotOpt {} // The purpose of NotOpt will become apparent below.
unsafe impl NotOpt for .. {}
impl<T> !NotOpt for Option<T> {}

impl<X> F_<X, F1> for () where X: NotOpt { type Type = X; }
impl<X> F_<Option<X>, F2> for () { type Type = X; }
// F can now be seen to be a type function that strips Option from a type.
// Note that these cases must be strictly disjoint in the "values" they accept, 
// otherwise the type inference will not succeed. Hence the use of NotOpt.

fn do_f<X, IT>() -> PhantomData<F<X, IT>> where (): F_<X, IT> { PhantomData }
// Function invocation is used as a mechanism to perform type inference for the
// IT parameter. Unfortunately there does not seem to be any other way to get
// this inference, which limits practical use.

fn same<T>(x: T, y: T) {} // helper function for validating the code

fn main() {
    // The IT parameter is inferred for the _ placeholders below.
    let x = do_f::<Option<bool>, _>(); // x is PhantomData<bool>
    let y = do_f::<bool, _>(); // y is PhantomData<bool>
    same(x, y); // compiles fine, since x and y are the same type
    // let z = do_f::<u32, _>();
    // same(x, z); // error - x and z are not the same type
    foo::<bool, _>();
}

// If the invocation relies on templated parameters, the constraint and IT
// parameter must be propagated outwards. If multiple invocations are used,
// the constraints and parameters can be coalesced using a helper trait to 
// prevent bloat in the function signature.
fn foo<T, IT>() where (): F_<T, IT> {
    let x = do_f::<T, IT>();
}