Crate lifted

Higher-kinded types for Rust.

This crate provides a safe higher-kinded type abstraction for use in Rust programs. The implementation is based on a suggestion by Joshua Liebow-Feeser in the blog post Rust has higher kinded types already… sort of, but written to be more general. These generalizations have produced largely the same scheme as described by Jeremy Yallop and Leo White in Lightweight higher-kinded polymorphism.

• The major components.
• Implementing higher-kinded functionality for a type.
• Using higher-kinded functionality.
• Using the built-in higher-kinded traits.
• Implementation details.

The major components.

There are three big pieces to write higher-kinded code with this library:

• Some type you wish to use in a higher-kinded way,
• A type representing the type constructor, implementing the type’s higher-kindedness, and
• Code that uses the type instances constructed with the type constructor.

The underlying implementation type can be user-defined or built-in; since we’re not implementing any traits on the implementation type itself there are no coherence concerns limiting what types we can extend this way.

The type constructor is represented by a phantom type, one that we never create an instance of. It implements one of the Kindn traits, depending on the kind signature. For a one-argument implementation type, such as Option<T> or Vec<T>, the type constructor would implement Kind1. For a two-argument implementation type, such as Result<T, E>, the type constructor would implement Kind2.

(n.b. such type constructors are provided in the types module, in case you’d like to use these standard types in a higher-kinded way. Look for OptionC, VecC, and ResultC.)

To use the type instances, work with one of the Kn structs, likewise depending on the kind signature. In the Option<T> case, you’d use K1<OptionC, T> to hold an instance. This can be freely converted back and forth between the wrapped representation and the implementation type with the new, inner, inner_mut, and into_inner methods.

Implementing higher-kinded functionality for a type.

To use a type constructor in a higher-kinded way, we will create a phantom type for the constructor. For example, to start to use the built-in Vec<*>, we create a constructor type VecC and specify how to create the relevant result type given the type parameter.

/// Phantom type constructor.
pub struct VecC;

impl<T> Kind1<T> for VecC {
    type Inner = Vec<T>;
}

Note that (roughly) this code is included in this library.

Using higher-kinded functionality.

The main use for a higher-kinded type is to declare a kind trait that various type constructors may implement. For instance, you can specify a Functor precisely:

pub trait Functor {
    fn fmap<A, B, F>(me: K1<Self, A>, f: F) -> K1<Self, B>
        where F: Fn(A) -> B;
}

This says that given two types, A and B, an instance of the type constructor applied to A, and a function to map between A and B, a Functor can produce an instance of the type constructor applied to B.

This kind trait could be implemented like this for the VecC type constructor:

impl Functor for VecC {
    fn fmap<A, B, F>(me: K1<Self, A>, f: F) -> K1<Self, B>
        where F: Fn(A) -> B
    {
        Self::new(              // re-wrap in helper type
            me.into_inner()     // unwrap helper type
                .into_iter()    // vec => iter
                .map(f)         // the actual map of fmap
                .collect()      // iter => vec
        )
    }
}

An academic example in this library (mostly useful for unit tests) includes the above Functor trait and VecC implementation.

Using the built-in higher-kinded traits.

You might feel tempted to use the built-in higher-kinded traits as some kind of Haskelly functional standard library. Consider that this might not be the best idea. This library has its uses, but rewriting everything to be based on category theory maybe isn’t the best thing to do.

Implementation details.

The implementation detail most likely to be important is that the data stored in a Kn helper struct is behind a heap allocation. This allows us to store the instance in an untyped pointer and cast to the appropriate instance.

Liebow-Feeser’s blog post proposes that each instance of the trait handle the unsafe unwrapping, but here we encapsulate that within the Kn helper structs.

Modules

applicative

The higher-kinded trait of an Applicative functor.

bifunctor

The higher-kinded trait of a Bifunctor.

functor

The higher-kinded trait of a Functor.

monad

The higher-kinded trait of a Monad.

transformer

The higher-kinded trait of a monad Transformer, as well as some basic transformer implementations.

types

Higher-kinded types for Rust standard library types.

Structs

K1

An instance of a type produced by a unary type constructor.

K2

An instance of a type produced by a binary type constructor.

K2P1_1

The left-applied specialization of a kind * -> * -> *.

K2P1_2

The right-applied specialization of a kind * -> * -> *.

Traits

Kind1

A type constructor of the kind * -> *.

Kind2

A type constructor of the kind * -> * -> *.