rust-coyoneda

通过科约内达引理实现函子组合

许可证

许可协议：

• Apache 许可证 2.0 版，(LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

任选其一。

贡献

除非您明确表示，否则根据 Apache-2.0 许可证定义的，您提交的任何有意包含在工作中的贡献，应按上述方式双许可，不附加任何额外条款或条件。

lib.rs:

通过科约内达引理实现函子组合

Rust 中的函子

让我们在 Rust 中实现函子！

考虑到没有高阶类型，我们的函子 trait 可能看起来像这样

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

当函数接受特定的类型作为函子时，这工作得很好，但无法编写一个操作通用函子类型并多次使用 fmap 的函数。例如，以下代码无法编译

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

虽然 Rust 的 trait 系统可以编码函子，但无法编码的是，函子 Box 将函数从 A 和 B 映射到函数从 Box<A> 到 Box<B>，而不是从 Box<A> 到 Option<B>。

特别是当考虑函子组合时，能够编码这一事实很有用，因为它允许我们链式调用多个 fmap 调用，并知道结果是另一个函子，可以进一步进行 fmap。

科约内达引理

让我们定义一个名为 Coyoneda 的数据类型

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

此数据类型是一个函子，它使用函数组合来累积映射函数，而不改变捕获的 T。对 Functor 的实现是微不足道的

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

共轭Yoneda引理表明，对于协变函子 f，此 Coyoneda f 与 f 自然同构。从实用角度来看，这意味着我们可以将任何 f a 升迁到 Coyoneda f a，并且给定一个函数 (a -> b) -> f b，我们可以从 Coyoneda f b 中检索到 f b。

组合Coyoneda

现在有一个问题：由于我们有一个与任何函子同构的参数化数据类型，我们可以将函子提升到Coyoneda中，以便在Rust的类型系统中安全地组合它们！

例如，让我们通过操作我们的 Coyoneda 类型来实现一个针对任何函子的泛型函数

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

鉴于我们为 Option 实现了函子，我们现在可以执行以下操作

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

... 或者对 Box

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

... 以及对其他每个函子也是如此。太棒了！