Higher-kinded type trait

hkt.rs

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);
}

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?

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