Skip to content

Instantly share code, notes, and snippets.

@badboy
Forked from 14427/hkt.rs
Created March 26, 2016 11:33
Show Gist options
  • Save badboy/6954cc6ce1c71b921094 to your computer and use it in GitHub Desktop.
Save badboy/6954cc6ce1c71b921094 to your computer and use it in GitHub Desktop.
Higher-kinded type trait
use std::rc::Rc;
pub 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);
pub 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)
}
}
pub 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 as HKT<U>>::T where Self: HKT<F>, F: Fn(&<Self as HKT<F>>::C) -> U;
}
impl<T, U> Applicative<U> for Option<T> {
fn pure_(value: U) -> <Self as HKT<U>>::T { Some(value) }
fn seq<F>(&self, fs: <Self as HKT<F>>::T) -> <Self as HKT<U>>::T where F: Fn(&<Self as HKT<F>>::C) -> 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) -> <Self as HKT<U>>::T { vec![value] }
fn seq<F>(&self, fs: <Self as HKT<F>>::T) -> <Self as HKT<U>>::T where F: Fn(&<Self as HKT<F>>::C) -> 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) -> <Self as HKT<U>>::T { Rc::new(value) }
fn seq<F>(&self, fs: <Self as HKT<F>>::T) -> <Self as HKT<U>>::T where F: Fn(&<Self as HKT<F>>::C) -> U {
let v = fs(self);
Rc::new(v)
}
}
impl<T, U> Applicative<U> for Box<T> {
fn pure_(value: U) -> <Self as HKT<U>>::T { Box::new(value) }
fn seq<F>(&self, fs: <Self as HKT<F>>::T) -> <Self as HKT<U>>::T where F: Fn(&<Self as HKT<F>>::C) -> U {
let v = fs(self);
Box::new(v)
}
}
pub 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)
}
}
pub 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) } }
#[cfg(test)]
mod test {
use std::rc::Rc;
use super::*;
pub struct Foo<T, P> where P: HKT<T> {
#[allow(unused)]
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 }
}
}
#[test]
fn test() {
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);
assert!(true);
}
}
@technetos
Copy link

I am pretty sure Applicative for Vec is implemented incorrectly.

It should be

impl<T, U> Applicative<U> for Vec<T> {
    fn pure_(value: U) -> Self::T {
        vec![value]
    }

    fn seq<F>(&self, fs: <Self as HKT<F>>::T) -> Vec<U>
    where
        F: Fn(&T) -> U,
    {
        let mut result = vec![];
        for f in fs.into_iter() {
            for x in self.iter() {
                let v = (f)(x);
                result.push(v);
            }
        }
        return result;
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment