Last active
November 18, 2020 16:56
-
-
Save mschuwalow/3f0dde829295280a6d9ba20743c712b7 to your computer and use it in GitHub Desktop.
Rust Functor Hierarchy
This file contains hidden or 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::marker::PhantomData; | |
trait Family<'a> { | |
type Member<T: 'a>: Mirror<'a, T, Family = Self>; | |
} | |
trait Mirror<'a, T> { | |
type Family: Family<'a>; | |
fn as_member(self) -> <Self::Family as Family<'a>>::Member<T>; | |
} | |
trait Functor<'a>: Family<'a> { | |
fn fmap<A: 'a, B: 'a, F: FnMut(A) -> B + 'a>( | |
fa: <Self as Family<'a>>::Member<A>, | |
f: F, | |
) -> <Self as Family<'a>>::Member<B>; | |
} | |
trait FunctorSyntax<'a, A: 'a, Fam: Functor<'a>>: | |
Mirror<'a, A, Family = Fam> + Sized | |
{ | |
fn fmap<B, F: FnMut(A) -> B + 'a>( | |
self, | |
f: F, | |
) -> <Fam as Family<'a>>::Member<B> { | |
<Fam as Functor>::fmap(self.as_member(), f) | |
} | |
} | |
impl<'a, A: 'a, F: Functor<'a>, T: Mirror<'a, A, Family = F>> | |
FunctorSyntax<'a, A, F> for T | |
{ | |
} | |
trait Applicative<'a>: Functor<'a> { | |
fn pure<A: 'a>(a: A) -> <Self as Family<'a>>::Member<A>; | |
fn zip<A: 'a, B: 'a>( | |
fa: <Self as Family<'a>>::Member<A>, | |
fb: <Self as Family<'a>>::Member<B>, | |
) -> <Self as Family<'a>>::Member<(A, B)>; | |
} | |
fn pure<'a, F: Applicative<'a>, A: 'a>(a: A) -> F::Member<A> { | |
<F as Applicative>::pure(a) | |
} | |
trait ApplicativeSyntax<'a, A: 'a, Fam: Applicative<'a>>: | |
Mirror<'a, A, Family = Fam> + Sized | |
{ | |
fn zip<B: 'a>( | |
self, | |
fb: <Fam as Family<'a>>::Member<B>, | |
) -> <Fam as Family<'a>>::Member<(A, B)> { | |
<Fam as Applicative>::zip(self.as_member(), fb) | |
} | |
} | |
impl<'a, A: 'a, F: Applicative<'a>, T: Mirror<'a, A, Family = F>> | |
ApplicativeSyntax<'a, A, F> for T | |
{ | |
} | |
// option | |
struct OptionFamily; | |
impl<'a> Family<'a> for OptionFamily { | |
type Member<T: 'a> = Option<T>; | |
} | |
impl<'a, A: 'a> Mirror<'a, A> for Option<A> { | |
type Family = OptionFamily; | |
fn as_member(self) -> Option<A> { | |
self | |
} | |
} | |
impl<'a> Functor<'a> for OptionFamily { | |
fn fmap<A, B, F: FnMut(A) -> B>(fa: Option<A>, f: F) -> Option<B> { | |
fa.map(f) | |
} | |
} | |
impl<'a> Applicative<'a> for OptionFamily { | |
fn pure<A>(a: A) -> Option<A> { | |
Some(a) | |
} | |
fn zip<A, B>(fa: Option<A>, fb: Option<B>) -> Option<(A, B)> { | |
match (fa, fb) { | |
(Some(a), Some(b)) => Some((a, b)), | |
_ => None, | |
} | |
} | |
} | |
// result | |
struct ResultFamily<'a, E: 'a> { | |
phantom: PhantomData<&'a E>, | |
} | |
impl<'a, E: 'a> Family<'a> for ResultFamily<'a, E> { | |
type Member<T: 'a> = Result<T, E>; | |
} | |
impl<'a, A: 'a, E: 'a> Mirror<'a, A> for Result<A, E> { | |
type Family = ResultFamily<'a, E>; | |
fn as_member(self) -> <Self::Family as Family<'a>>::Member<A> { | |
self | |
} | |
} | |
impl<'a, E: 'a> Functor<'a> for ResultFamily<'a, E> { | |
fn fmap<A, B, F: FnMut(A) -> B>(fa: Result<A, E>, f: F) -> Result<B, E> { | |
fa.map(f) | |
} | |
} | |
impl<'a, E: 'a> Applicative<'a> for ResultFamily<'a, E> { | |
fn pure<A>(a: A) -> Result<A, E> { | |
Ok(a) | |
} | |
fn zip<A, B>(fa: Result<A, E>, fb: Result<B, E>) -> Result<(A, B), E> { | |
fa.and_then(|a| fb.map(|b| (a, b))) | |
} | |
} | |
// iterator | |
struct IteratorWrap<'a, T>(Box<dyn Iterator<Item = T> + 'a>); | |
trait IteratorSyntax<'a, T: Sized>: Iterator<Item = T> + Sized + 'a { | |
fn wrap(self) -> IteratorWrap<'a, T> { | |
IteratorWrap(Box::new(self)) | |
} | |
} | |
impl<'a, T, I: Iterator<Item = T> + 'a> IteratorSyntax<'a, T> for I {} | |
impl<'a, T> Iterator for IteratorWrap<'a, T> { | |
type Item = T; | |
fn next(&mut self) -> Option<Self::Item> { | |
self.0.next() | |
} | |
} | |
struct IteratorWrapFamily; | |
impl<'a> Family<'a> for IteratorWrapFamily { | |
type Member<T: 'a> = IteratorWrap<'a, T>; | |
} | |
impl<'a, T: 'a> Mirror<'a, T> for IteratorWrap<'a, T> { | |
type Family = IteratorWrapFamily; | |
fn as_member(self) -> <Self::Family as Family<'a>>::Member<T> { | |
self | |
} | |
} | |
impl<'a> Functor<'a> for IteratorWrapFamily { | |
fn fmap<A: 'a, B, F: FnMut(A) -> B + 'a>( | |
fa: IteratorWrap<'a, A>, | |
f: F, | |
) -> IteratorWrap<'a, B> { | |
IteratorWrap(Box::new(fa.0.into_iter().map(f).into_iter())) | |
} | |
} | |
impl<'a> Applicative<'a> for IteratorWrapFamily { | |
fn pure<A: 'a>(a: A) -> IteratorWrap<'a, A> { | |
vec![a].into_iter().wrap() | |
} | |
fn zip<A: 'a, B: 'a>( | |
fa: IteratorWrap<A>, | |
fb: IteratorWrap<B>, | |
) -> IteratorWrap<'a, (A, B)> { | |
let mut result = Vec::new(); | |
let mut fa = fa; | |
let mut fb = fb; | |
while let (Some(a), Some(b)) = (fa.next(), fb.next()) { | |
result.push((a, b)); | |
} | |
result.into_iter().wrap() | |
} | |
} | |
// usage | |
fn use_applicative<'a, A, F: Applicative<'a>>(a: A, b: A) -> F::Member<(A, A)> { | |
let fa = pure::<F, _>(a); | |
let fb = pure::<F, _>(b); | |
fa.zip(fb) | |
} | |
fn foo() -> Option<(i32, i32)> { | |
let a = Some(3); | |
let b = a.fmap(|x| (x + 1, x)); | |
b | |
} | |
fn use_iterator() -> IteratorWrap<'static, i32> { | |
let v = vec![1]; | |
v.into_iter().wrap().fmap(|x| x + 1).fmap(|x| x + 1) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment