Last active
August 31, 2024 00:57
-
-
Save 14427/af90a21b917d2892eace 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; | |
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); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I made it compile with latest stable Rust: https://gist.github.com/badboy/6954cc6ce1c71b921094 (though I don't understand much of the code yet)