# [−][src]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 |

bifunctor | The higher-kinded trait of a |

functor | The higher-kinded trait of a |

monad | The higher-kinded trait of a |

transformer | The higher-kinded trait of a monad |

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 |