-
-
Save badboy/6954cc6ce1c71b921094 to your computer and use it in GitHub Desktop.
Higher-kinded type trait
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
See the revisions
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
What did you change?