Skip to content

Instantly share code, notes, and snippets.

@14427
Last active August 31, 2024 00:57
Show Gist options
  • Save 14427/af90a21b917d2892eace to your computer and use it in GitHub Desktop.
Save 14427/af90a21b917d2892eace to your computer and use it in GitHub Desktop.
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
Copy link

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
Copy link

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
Copy link

Sgeo 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
Copy link

badboy 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