rust-coyoneda

Functor composition via the Co-Yoneda Lemma

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

lib.rs:

Functor composition via the Co-Yoneda Lemma

Functors in Rust

Let's implement functors in Rust!

Working around the lack of higher-kinded types, our trait for a functor will look something like this:

pub trait Param { type Param; }
pub trait ReParam<B>: Param { type Output: Param<Param=B>; }
pub trait Functor<'a, B>: ReParam<B> {
    fn fmap<F: Fn(Self::Param) -> B + 'a>(self, F) -> Self::Output;
}

This works great as long as we write functions that take specific types which are functors, but it is not possible to write a function operating on a generic functor type and using fmap more than once. For example, the following will not compile:

fn add_and_to_string<'a, F>(x: F) -> <F as ReParam<String>>::Output
   where F: Param<Param=i32> + Functor<'a, i32> + Functor<'a, String> {
   x.fmap(|n: i32| n + 1)
    .fmap(|n: i32| n.to_string())
}

While functors in general can be encoded to some extend in Rust's trait system, what we can't encode for a lack of higher-kinded types, is the fact that a functor Box maps a function between A and B to a function between Box<A> and Box<B>, not between Box<A> and Option<B>.

Especially when looking at functor composition, it is useful to be able to encode this fact, because it allows us to chain multiple calls to fmap, knowing that the result is also a functor, and can be fmap'ed further.

The Co-Yoneda Lemma

Let's define a data type called Coyoneda:

pub struct Coyoneda<'a, T: Param, B> {
    point: T,
    morph: Fn(T::Param) -> B + 'a
}

This datatype is a functor, which uses function composition to accumulate the mapping function, without changing the captured T. The implementation for Functor is trivial:

impl<'a, T: Param, B, C> Functor<'a, C> for Coyoneda<'a, T, B> {
    type Output = Coyoneda<'a, T, C>;
    fn fmap<F: Fn(B) -> C + 'a>(self, f: F) -> Coyoneda<'a, T, C> {
        let g = self.morph;
        Coyoneda{point: self.point, morph: move |x| f(g(x))}
    }
}

The co-yoneda lemma states that for a covariant functor f, this Coyoneda f is naturally isomorphic to f. Practically speaking, this means that we can lift any f a into a Coyoneda f a, and given a function (a -> b) -> f b, we can retrieve back a f b from a Coyoneda f b.

Composing Coyoneda

Now here's the catch: Since we have a parameterized datatype that is isomorphic to any functor, we can lift functors into Coyoneda to compose them safely within Rust's type system!

For example, let's implement a function that is generic for any functor, by operating on our Coyoneda type:

fn add_and_to_string<T: Param>(y: Coyoneda<T, i32>) -> Coyoneda<T, String> {
   y.fmap(|n: i32| n + 1)
    .fmap(|n: i32| n.to_string())
}

Given we implemented a functor for Option, we can now do the following:

let y = add_and_to_string(From::from(Some(42)));
assert_eq!(y.unwrap(), Some("43".to_string()))

... or for Box:

let y = add_and_to_string(From::from(Box::new(42)));
assert_eq!(y.unwrap(), Box::new("43".to_string()))

... and for every other functor as well. Yay!