Im Zusammenhang mit dem Typsystem tauchen die Begriffe Typ, Lebenszeit und Typkonstruktor auf. Um diese Begriffe in vereinheitlichter Weise systematisch erfassen zu können, führt man das Konzept der Arten, engl. kinds, ein.
Die gewöhnliche Art von Typen nennen wir Type.
Darin enthalten sind alle Typen wie bool,
i32 und Werte von Typkonstruktoren wie
Option<i32> und Vec<i32>.
Auch &'a [i32] ist für eine konkrete Lebenszeit
'a der Wert eines Typkonstruktors, und damit ebenfalls in
dieser Art enthalten.
Daneben gibt es die Art der Lebenszeiten, nennen wir sie
Region. Darin enthalten sind alle Lebenszeiten,
von denen 'static eine benennbare ist.
Die Typen der beiden Arten Type und Region
kann man als nullstellige, das heißt argumentlose Typkonstruktoren
betrachten.
Die Art Type -> Type umfasst alle einstelligen
Typkonstruktoren. Darin enthalten sind bspw. Option,
Vec und der Array-Konstruktor zur Länge N,
der jedem Typ T den Array-Typ [T;N]
zuordnet. Außerdem enthalten sind aus partieller Applikation
mehrstelliger Typkonstruktoren entstandene einstellige
Typkonstruktoren wie io::Result.
Rust unterstützt keine höher gearteten Typen, engl. higher kinded types, kurz HKT. Allerdings ist es möglich, HKT unter Ausnutzung des Trait-Systems zu emulieren[1][2], und dies sogar ohne Bemühung generischer assoziierter Typen[3].
Zwei Dinge sind hier zu beachten:
F ist kein Konstruktor,
womit das Vorhandensein der Applikation F<X>
entfällt. Aus diesem Grund müssen wir eine
Typ-Defunktionalisierung vornehmen, bei der
F<X> gegen App<F,X>
ersetzt wird.
Die Applikation kodieren wir so:
trait AppliedTo<X> {
type Value;
}
type App<F, X> = <F as AppliedTo<X>>::Value;
Die Stellvertreter für Option
und Vec:
struct OptionType;
impl<X> AppliedTo<X> for OptionType {
type Value = Option<X>;
}
struct VecType;
impl<X> AppliedTo<X> for VecType {
type Value = Vec<X>;
}
Nun können wir die klassischen Beispiele Functor
und Monad auf allgemeine Weise implementieren.
Zunächst Functor:
trait Functor<X, Y>: AppliedTo<X> + AppliedTo<Y> {
fn map<F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> Y, F: Copy;
}
impl<X, Y> Functor<X, Y> for OptionType {
fn map<F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> Y
{
x.map(f)
}
}
impl<X, Y> Functor<X, Y> for VecType {
fn map<F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> Y
{
x.into_iter().map(f).collect()
}
}
fn main() {
let x = Some(0);
println!("{:?}", OptionType::map(x, |x| x + 1));
let x = vec![1, 2, 3, 4];
println!("{:?}", VecType::map(x, |x| x + 1));
}
Damit ist es nun machbar, Funktionen über Typkonstruktoren zu parametrisieren:
fn add1<F: Functor<i32, i32>>(x: App<F, i32>) -> App<F, i32> {
F::map(x, |x| x + 1)
}
fn main() {
let x = Some(0);
println!("{:?}", add1::<OptionType>(x));
let x = vec![1, 2, 3, 4];
println!("{:?}", add1::<VecType>(x));
}
Es folgt Monad. Die Funktion
unit zieht man am besten aus Monad
heraus in einen separaten Trait, weil Monad
die Typparameter von bind enthält, die man
für unit nicht braucht.
trait Unit<X> where Self: AppliedTo<X> {
fn unit(x: X) -> App<Self, X>;
}
trait Monad<X, Y> where Self: Unit<X> + Unit<Y> {
fn bind<F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> App<Self, Y>, F: Copy;
}
impl<X> Unit<X> for OptionType {
fn unit(x: X) -> App<Self, X> {Some(x)}
}
impl<X, Y> Monad<X, Y> for OptionType {
fn bind<F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> App<Self, Y>
{
x.and_then(f)
}
}
impl<X> Unit<X> for VecType {
fn unit(x: X) -> App<Self, X> {vec![x]}
}
impl<X, Y> Monad<X, Y> for VecType {
fn bind<F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> App<Self, Y>
{
x.into_iter().flat_map(f).collect()
}
}
fn main() {
let x = OptionType::unit(0);
println!("{:?}", OptionType::bind(x, |x| Some(x + 1)));
}
Die allgemeine Implementierung von join:
fn join<M, X>(mmx: App<M, App<M, X>>) -> App<M, X>
where M: Monad<App<M, X>, X>
{
M::bind(mmx, |mx| mx)
}
fn main() {
let x = Some(Some(0));
println!("{:?}", join::<OptionType,_>(x));
}
bzw.
trait Join<X> where Self: AppliedTo<X> + AppliedTo<App<Self, X>> {
fn join(mmx: App<Self, App<Self, X>>) -> App<Self, X>;
}
impl<M, X> Join<X> for M where M: Monad<App<M, X>, X> {
fn join(mmx: App<Self, App<Self, X>>) -> App<Self, X> {
M::bind(mmx, |mx| mx)
}
}
fn main() {
let x: Some(Some(0));
println!("{:?}", OptionType::join(x));
}
Kartesisches Produkt von Monaden:
fn prod<M, X, Y>(mx: App<M, X>, my: App<M, Y>) -> App<M, (X, Y)>
where
M: Monad<X, (X, Y)> + Monad<Y, (X, Y)>,
X: Clone, App<M, Y>: Clone
{
M::bind(mx, |x: X|
M::bind(my.clone(), |y| M::unit((x.clone(), y))))
}
fn main() {
let a = vec!["x", "y"];
let b = vec![1, 2];
println!("{:?}", prod::<VecType, _, _>(a, b));
}
bzw.
trait Prod<X, Y> {
fn prod(mx: App<Self, X>, my: App<Self, Y>) -> App<Self, (X, Y)>
where Self: AppliedTo<X> + AppliedTo<Y> + AppliedTo<(X, Y)>;
}
impl<M, X, Y> Prod<X, Y> for M
where
M: Monad<X, (X, Y)> + Monad<Y, (X, Y)>,
X: Clone, App<M, Y>: Clone
{
fn prod(mx: App<M, X>, my: App<M, Y>) -> App<M, (X, Y)>
{
M::bind(mx, |x: X|
M::bind(my.clone(), |y| M::unit((x.clone(), y))))
}
}
fn main() {
let a = vec!["x", "y"];
let b = vec![1, 2];
println!("{:?}", VecType::prod(a, b));
}
Alternativ zum gezeigten Ansatz lassen sich die Typparameter der Traits auch zu den Funktionen hin verschieben, wodurch meines Erachtens mehr Klarheit geschaffen wird.
trait Functor {
fn map<X, Y, F>(x: App<Self, X>, f: F) -> App<Self, Y>
where
F: Fn(X) -> Y, F: Copy,
Self: AppliedTo<X> + AppliedTo<Y>;
}
impl Functor for OptionType {
fn map<X, Y, F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> Y
{
x.map(f)
}
}
impl Functor for VecType {
fn map<X, Y, F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> Y
{
x.into_iter().map(f).collect()
}
}
trait Monad {
fn unit<X>(x: X) -> App<Self, X> where Self: AppliedTo<X>;
fn bind<X, Y, F>(x: App<Self, X>, f: F) -> App<Self, Y>
where
F: Fn(X) -> App<Self, Y>, F: Copy,
Self: AppliedTo<X> + AppliedTo<Y>;
}
impl Monad for OptionType {
fn unit<X>(x: X) -> App<Self, X> {Some(x)}
fn bind<X, Y, F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> App<Self, Y>
{
x.and_then(f)
}
}
impl Monad for VecType {
fn unit<X>(x: X) -> App<Self, X> {vec![x]}
fn bind<X, Y, F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> App<Self, Y>
{
x.into_iter().flat_map(f).collect()
}
}
Der Compiler bekommt jetzt allerdings irgendwie Probleme mit der
Typinferenz in join, weshalb der zweite
Typparameter von bind manuell festgelegt werden muss:
fn join<M, X>(mmx: App<M,App<M, X>>) -> App<M, X>
where M: Monad + AppliedTo<X> + AppliedTo<App<M, X>>
{
M::bind::<_, X, _>(mmx, |mx| mx)
}
Bei einem mehrstelligen Typkonstruktor wie
Result<X,E> kann man den Stellvertreter
über das nebensächliche Argument E parametrisieren.
Dies entspricht der partiellen Applikation des Typkonstruktors.
use std::marker::PhantomData as Ph;
struct ResultType<E> {ph: Ph<E>}
impl<X, E> AppliedTo<X> for ResultType<E> {
type Value = Result<X, E>;
}
impl<E> Functor for ResultType<E> {
fn map<X, Y, F>(x: App<Self, X>, f: F) -> App<Self, Y>
where F: Fn(X) -> Y
{
x.map(f)
}
}
Bei der Implementierung einer Warteschlange mittels zweier Stapel soll von der genutzten Implementierung des Stapels abstrahiert werden, dergestalt dass sich der Typ des Stapels gegen einen anderen austauschen lässt, ohne die Implementierung der Warteschlange modifizieren zu müssen.
Das Modulsystem der Sprache Standard ML wurde extra dafür entworfen, solcherlei Abstraktionen durchführen zu können. Die Schnittstelle einer Funktionalität ist dabei durch eine sogenannte Signatur gegeben. Rust bietet mit den Traits ein ähnliches Sprachmittel zur Beschreibung von Schnittstellen.
Zunächst erfolgt eine Formulierung mit HKT, um den Typkonstruktor des Stapels als Typparameter nutzen zu können.
pub trait AppliedTo<X> {
type Value;
}
type App<F, X> = <F as AppliedTo<X>>::Value;
mod stack {
use super::{App, AppliedTo};
pub trait Stack<T>: AppliedTo<T> {
fn new() -> App<Self, T>;
fn push(pself: &mut App<Self, T>, x: T);
fn pop(pself: &mut App<Self, T>) -> Option<T>;
fn is_empty(pself: &App<Self, T>) -> bool;
}
pub struct VecStack<T>(Vec<T>);
pub struct VecStackType;
impl<X> AppliedTo<X> for VecStackType {
type Value = VecStack<X>;
}
impl<T> Stack<T> for VecStackType {
fn new() -> VecStack<T> {
VecStack(Vec::new())
}
fn push(pself: &mut VecStack<T>, x: T) {
pself.0.push(x);
}
fn pop(pself: &mut VecStack<T>) -> Option<T> {
pself.0.pop()
}
fn is_empty(pself: &VecStack<T>) -> bool {
pself.0.is_empty()
}
}
}
mod queue {
use super::stack::Stack;
use super::App;
pub struct Queue<T, S: Stack<T>> {
istack: App<S, T>,
ostack: App<S, T>
}
impl<T, S: Stack<T>> Queue<T, S> {
pub fn new() -> Self {
Self {istack: S::new(), ostack: S::new()}
}
pub fn enqueue(&mut self, x: T) {
S::push(&mut self.istack, x)
}
pub fn dequeue(&mut self) -> Option<T> {
if S::is_empty(&self.ostack) {
while let Some(x) = S::pop(&mut self.istack) {
S::push(&mut self.ostack, x)
}
}
S::pop(&mut self.ostack)
}
}
}
type Queue<T> = queue::Queue<T, stack::VecStackType>;
fn main() {
let mut q: Queue<i32> = Queue::new();
q.enqueue(1);
q.enqueue(2);
println!("{:?}", q.dequeue());
println!("{:?}", q.dequeue());
}
Dass die Nutzung höher gearteter Typen in diesem Fall entbehrlich ist, zeigt die nächste ergonomischere Formulierung, die die Warteschlange nicht durch den Typkonstruktor parametrisiert, sondern durch dessen Wert. Zur Aufhübschung der Notation wird der Elementtyp dabei nicht als Typparameter der Warteschlange notiert, sondern als assoziierter Typ der Schnittstelle zum Stapel.
mod stack {
pub trait Stack {
type Item;
fn new() -> Self;
fn push(&mut self, x: Self::Item);
fn pop(&mut self) -> Option<Self::Item>;
fn is_empty(&self) -> bool;
}
pub struct VecStack<T>(Vec<T>);
impl<T> Stack for VecStack<T> {
type Item = T;
fn new() -> Self {
VecStack(Vec::new())
}
fn push(&mut self, x: T) {
self.0.push(x);
}
fn pop(&mut self) -> Option<T> {
self.0.pop()
}
fn is_empty(&self) -> bool {
self.0.is_empty()
}
}
}
mod queue {
use super::stack::Stack;
pub struct Queue<S: Stack> {
istack: S,
ostack: S
}
impl<S: Stack> Queue<S> {
pub fn new() -> Self {
Self {istack: S::new(), ostack: S::new()}
}
pub fn enqueue(&mut self, x: S::Item) {
self.istack.push(x)
}
pub fn dequeue(&mut self) -> Option<S::Item> {
if self.ostack.is_empty() {
while let Some(x) = self.istack.pop() {
self.ostack.push(x)
}
}
self.ostack.pop()
}
}
}
type Queue<T> = queue::Queue<stack::VecStack<T>>;
fn main() {
let mut q: Queue<i32> = Queue::new();
q.enqueue(1);
q.enqueue(2);
println!("{:?}", q.dequeue());
println!("{:?}", q.dequeue());
}