Skip to content

Instantly share code, notes, and snippets.

@14427 14427/hkt.rs
Last active May 25, 2019

Embed
What would you like to do?
Higher-kinded type trait
use std::rc::Rc;
trait HKT<U> {
type C; // Current type
type T; // Type with C swapped with U
}
macro_rules! derive_hkt {
($t:ident) => {
impl<T, U> HKT<U> for $t<T> {
type C = T;
type T = $t<U>;
}
}
}
derive_hkt!(Vec);
derive_hkt!(Option);
derive_hkt!(Box);
derive_hkt!(Rc);
trait Functor<U>: HKT<U> {
fn map<F>(&self, f: F) -> Self::T where F: Fn(&Self::C) -> U;
}
impl<T, U> Functor<U> for Vec<T> {
fn map<F>(&self, f: F) -> Vec<U> where F: Fn(&T) -> U {
let mut result = Vec::with_capacity(self.len());
for value in self {
result.push( f(value) );
}
result
}
}
impl<T, U> Functor<U> for Option<T> {
fn map<F>(&self, f: F) -> Option<U> where F: Fn(&T) -> U {
match *self {
Some(ref value) => Some( f(value) ),
None => None,
}
}
}
impl<T, U> Functor<U> for Rc<T> {
fn map<F>(&self, f: F) -> Rc<U> where F: Fn(&T) -> U {
let v = f(self);
Rc::new(v)
}
}
impl<T, U> Functor<U> for Box<T> {
fn map<F>(&self, f: F) -> Box<U> where F: Fn(&T) -> U {
let v = f(self);
Box::new(v)
}
}
trait Applicative<U>: Functor<U> {
fn pure_(value: U) -> Self::T where Self: HKT<U, C=U>;
fn seq<F>(&self, <Self as HKT<F>>::T) -> Self::T where F: Fn(&Self::C) -> U;
}
impl<T, U> Applicative<U> for Option<T> {
fn pure_(value: U) -> Option<U> { Some(value) }
fn seq<F>(&self, fs: Option<F>) -> Option<U> where F: Fn(&T) -> U {
match *self {
Some(ref value) => match fs {
Some(f) => Some( f(value) ),
None => None,
},
None => None,
}
}
}
impl<T, U> Applicative<U> for Vec<T> {
fn pure_(value: U) -> Vec<U> { vec![value] }
fn seq<F>(&self, fs: Vec<F>) -> Vec<U> where F: Fn(&T) -> U {
let mut result = vec![];
for (i, f) in fs.into_iter().enumerate() {
let v = (f)( &self[i] );
result.push(v)
}
return result;
}
}
impl<T, U> Applicative<U> for Rc<T> {
fn pure_(value: U) -> Rc<U> { Rc::new(value) }
fn seq<F>(&self, fs: Rc<F>) -> Rc<U> where F: Fn(&T) -> U {
let v = fs(self);
Rc::new(v)
}
}
impl<T, U> Applicative<U> for Box<T> {
fn pure_(value: U) -> Box<U> { Box::new(value) }
fn seq<F>(&self, fs: Box<F>) -> Box<U> where F: Fn(&T) -> U {
let v = fs(self);
Box::new(v)
}
}
trait Monad<U>: Applicative<U> {
fn bind<F>(&self, F) -> Self::T where F : FnMut(&Self::C) -> Self::T;
fn return_(x: U) -> Self::T where Self: HKT<U, C=U> {
Self::pure_(x)
}
fn join<T>(&self) -> T where Self: HKT<U, T=T, C=T>, T: Clone {
self.bind(|x| x.clone())
}
}
impl<T, U> Monad<U> for Vec<T> {
fn bind<F>(&self, mut f: F) -> Vec<U> where F : FnMut(&T) -> Vec<U> {
let mut result = vec![];
for x in self {
let v = f(x);
result.extend(v);
}
result
}
}
impl<T, U> Monad<U> for Option<T> {
fn bind<F>(&self, mut f: F) -> Option<U> where F : FnMut(&T) -> Option<U> {
match *self {
Some(ref value) => f(value),
None => None,
}
}
}
impl<T, U> Monad<U> for Rc<T> {
fn bind<F>(&self, mut f: F) -> Rc<U> where F: FnMut(&T) -> Rc<U> {
f(self)
}
}
impl<T, U> Monad<U> for Box<T> {
fn bind<F>(&self, mut f: F) -> Box<U> where F: FnMut(&T) -> Box<U> {
f(self)
}
}
trait New<T> {
fn new(T) -> Self;
}
impl<T> New<T> for Box<T> { fn new(v: T) -> Box<T> { Box::new(v) } }
impl<T> New<T> for Rc<T> { fn new(v: T) -> Rc<T> { Rc::new(v) } }
struct Foo<T, P> where P: HKT<T> {
ptr: P::T
}
impl<T, P> Foo<T, P> where P: HKT<T, C=()>, P::T: New<T> {
fn new(v: T) -> Self {
let p: P::T = P::T::new(v);
Foo { ptr: p }
}
}
fn main() {
let v = Vec::return_(1);
let v = v.bind(|x| vec![x.to_string(); 3]);
println!("{:?}", v);
let o = Option::return_(1);
let o = o.bind(|&x| Some(x + 1));
println!("{:?}", o);
let o = Option::pure_(1);
let o = o.bind(|&x| Some(x + 1));
println!("{:?}", o);
let rc = Rc::return_(7);
let rc = rc.bind(|&x| Rc::new(x * 3));
println!("{:?}", rc);
let b = Box::return_(7);
let b = b.bind(|&x| Box::new(x * 4));
println!("{:?}", b);
let o = Some(Some(true));
let o = o.join();
println!("{:?}", o);
let v = vec![vec!(true), vec!(false)];
let v = v.join();
println!("{:?}", v);
let f1: &Fn(&i32) -> i32 = &|x| x*3;
let f = Some(f1);
let o = Some(3);
let o = o.seq(f);
println!("{:?}", o);
let f: Foo<_, Box<_>> = Foo::new(5);
let p: Box<_> = f.ptr;
println!("{:?}", p);
let f: Foo<_, Rc<_>> = Foo::new("5".to_string());
let p: Rc<_> = f.ptr;
println!("{:?}", p);
}
@infinity0

This comment has been minimized.

Copy link

commented Sep 3, 2015

Current rust nightly complains about <Self as HKT<F>>::T in Applicative::seq<F>, says that the trait 'HKT<F>' is not implemented for the type 'Self'. Any ideas on how to fix this?

@infinity0

This comment has been minimized.

Copy link

commented Sep 4, 2015

Looks like this works, for now:

fn seq<F>(&self, <Self as HKT<F>>::T) -> <Self as HKT<U>>::T where
  F: Fn(&<Self as HKT<U>>::C) -> U, Self: HKT<F>;

It's getting ugly though. Also, in the impls you need to declare (e.g.) -> Self::T instead of -> Option<U>.

@Sgeo

This comment has been minimized.

Copy link

commented Mar 25, 2016

Any plans to make this into a crate? The current hkt crate on crates.io relies on shoggoth.

Also, may I suggest renaming ::C and ::T into something easier to read at a glance? And perhaps type aliases, like type Base<T> = <T as HKT<()>>::C?

@badboy

This comment has been minimized.

Copy link

commented Mar 26, 2016

I made it compile with latest stable Rust: https://gist.github.com/badboy/6954cc6ce1c71b921094 (though I don't understand much of the code yet)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.