haskell_bits

Haskell的各种类型类和概念在Rust中的实现。 (crates.io链接)

概述

目前这个库是Rust中Functor/Applicative/Monad层次的实现。它是一个非常正在进行中的项目，我现在发布它主要是作为一个征求意见，我希望能与大家讨论我的设计选择，在走得太远之前。

在这个领域已经有一些工作，例如

• fp-core
• frunk
• functional

那么，这个库有什么不同之处呢？!

我认为这个库独特之处在于可以在Monads，Applicatives，Functors等上定义泛型函数。

上面提到的库似乎为各种类型定义了Functor，Applicative，Monad，所以fmap，bind等在这些类型上工作，但似乎没有一种方法可以编写一个适用于所有类型定义的泛型函数，例如Monad。

我认为这是一个非常重要的问题。这些类型类如Haskell中的Monad的伟大之处在于，如果你有m个不同的Monads和n个定义在Monads上的函数，你现在就有了实质上m*n个函数定义。创建一个新的Monad，你就得到了一个巨大的基础设施。创建一个新的Monad函数，它就可以在由其他人已经定义的100多个Monadic类型上工作。

这是Monads和相关概念，以及更广泛的Haskell，之所以如此强大的关键之一，因为你可以以乘法数量的方式组合事物，如此之多，以至于许多问题只是将现有的代码块组合在一起，类型系统确保你可以安全地这样做，而且几乎总是正确。这在生产力方面是一个巨大的优势，特别是在可靠性方面。

示例

这是一个简单的Haskell函数

monadic_pair :: Monad m => m a -> m a -> m (a, a)
monadic_pair x y = do
    x_val <- x
    y_val <- y
    pure (x_val, y_val)

这是在Rust中使用这个库的等效函数

fn monadic_pair<TCon, T, TArg>(x: &TArg, y: &TArg) -> <TCon as WithTypeArg<(T, T)>>::Type
where
    TCon: Monad + WithTypeArg<T> + WithTypeArg<(T, T)>,
    TArg: TypeApp<TCon, T>,
    T: Clone,
{
    mdo! {
        x_val =<< x;
        y_val =<< y;
        ret<TCon> (x_val.clone(), y_val.clone());
    }
}

然后我们可以将其应用于向量

let v1: Vec<u32> = vec![1, 2, 3];
let v2: Vec<u32> = vec![4, 5, 6];        
let v_result = monadic_pair(&v1, &v2);

assert_eq!(
    v_result,
    vec![
        (1, 4),
        (1, 5),
        (1, 6),
        (2, 4),
        (2, 5),
        (2, 6),
        (3, 4),
        (3, 5),
        (3, 6)
    ]
);

或选项

let o1: Option<u32> = Some(1);
let o2: Option<u32> = Some(2);
let o3: Option<u32> = None;

let o1_result = monadic_pair(&o1, &o2);
let o2_result = monadic_pair(&o1, &o3);

assert_eq!(o1_result, Some((1, 2)));
assert_eq!(o2_result, None);

所有结果都是预期的。

我们甚至可以进行标准的Applicative风格函数应用

let _applicative_option_result = (|x| move |y| x + y).lmap(o1).lap(o2);
assert_eq!(Some(3), _applicative_option_result);

但我会稍后提到一些注意事项。

它是如何工作的呢？

Rust 没有高阶类型，至少我们没有可以抽象的类型。我的意思是，虽然 Rust 允许使用一些泛型 T 的 Vec<T>，但 Rust 不允许 T<u32>。它允许 Vec<u32>，但我们不能像 u32 一样对 Vec 进行抽象。

这带来了一些特定的后果。比如说，我们想在 Rust 中编写一个 trait，封装对结构体所有部分应用函数的想法。我们可能会尝试这样做：

trait Mappable {
  map<TIn, TOut>(f: impl Func<TIn, TOut>, x: Self<TIn>) -> Self<TOut>;
}

impl Mappable for Vec {
  ...
}

impl Mappable for Option {
  ...
}

// etc...

一个小问题

但是我们不能这样做。Rust 会拒绝编译这段代码，因为 Vec、Option（以及隐式地 Self）不是类型。虽然 Option<u32> 是，但 Option 不是。

所以我们需要做一些技巧

pub trait WithTypeArg<T>
{
    type Type;
}

然后

pub struct VecTypeCon;

impl<T> WithTypeArg<T> for VecTypeCon {
    type Type = Vec<T>;
}

我们可以这样定义 Mappable

pub trait Mappable {
    fn map<TIn, TOut>(
        f: impl Fn(TIn) -> TOut,
        x: <Self as WithTypeArg<TIn>>::Type,
    ) -> <Self as WithTypeArg<TOut>>::Type
}

这是为 Option 提供的一个简单实现

impl Mappable for OptionTypeCon {
    fn lmap<TIn, TOut>(
        f: impl Fn(TIn) -> TOut,
        x: <OptionTypeCon as WithTypeArg<TIn>>::Type,
    ) -> <OptionTypeCon as WithTypeArg<TOut>>::Type {
        Option::map(x, f) // Option itself already has a specific "map" function
    }
}

以及为 Vec 提供的实现

impl Mappable for VecTypeCon {
    fn map<TIn, TOut>(
        f: impl Fn(TIn) -> TOut,
        x: <VecTypeCon as WithTypeArg<TIn>>::Type,
    ) -> <VecTypeCon as WithTypeArg<TOut>>::Type {
        let size = x.capacity();
        let mut v: Vec<TOut> = Vec::with_capacity(size);
        for e in x {
            v.push(f(e));
        }
        v
    }
}

到目前为止，这已经很好了，但有一个小问题，我们解决了。

注意，这个库的主要动机是能够以泛化的方式组合这些函数。

好，让我们做一个愚蠢的函数，它只是连续进行两次映射（这个函数很愚蠢，因为它可以通过合并函数来更有效地执行，但我们还是这么做吧）

fn map2<TCon, TIn, TMid, TOut>(
    f: impl Fn(TIn) -> TMid,
    g: impl Fn(TMid) -> TOut,
    x: <TCon as WithTypeArg<TIn>>::Type,
) -> <TCon as WithTypeArg<TOut>>::Type
{
    map(g, map(f, x))
}

不幸的是，这个函数不起作用，尽管它看起来类型是正确的。我认为这是因为 Rust 除非类型完全解析，否则不会对类型进行匹配，而 <TCon as WithTypeArg<TIn>>::Type 不能解析，因为我们不知道 TCon 或 TIn 是什么。因此，我们不能将其传递给 map，即使它需要一个 <TCon as WithTypeArg<TIn>>::Type（完全相同的东西）作为参数，因为我认为 Rust 想在检查它们是否相等之前解析它们。

所以我们调整了 WithTypeArg 的定义

pub trait WithTypeArg<T> {
    type Type: TypeApp<Self, T>;
}

然后编写这个新的 trait TypeApp

pub trait TypeApp<TCon, T>
where
    TCon: WithTypeArg<T>,
    Self: Is<Type = <TCon as WithTypeArg<T>>::Type>,
{
}

是的，注意这些 trait 互相引用。重要的是 Is trait。这需要一些思考，我建议查看我的 is_type 库的源代码。但基本上，这允许一个人在 trait 和实际类型之间强制建立一对一的对应关系。

所以你可以随心所欲地在它们之间来回转换。

然后我们可以按照以下方式重新定义 map，替换掉任何 TCon 的参数（但不是返回类型）

<作为作为 具有类型参数<T>>::类型

with

实现 类型应用<TCon, T>

pub trait Mappable {
    fn map<TIn, TOut>(
        f: impl Fn(TIn) -> TOut,
        x: impl TypeApp<TCon, TIn>,
    ) -> <Self as WithTypeArg<TOut>>::Type
}

和类似地更改 map2

fn map2<TCon, TIn, TMid, TOut>(
    f: impl Fn(TIn) -> TMid,
    g: impl Fn(TMid) -> TOut,
    x: impl TypeApp<TCon, TIn>,
) -> <TCon as WithTypeArg<TOut>>::Type
{
    map(g, map(f, x))
}

我们就成功了。

似乎由于某种原因没有将 <TCon as WithTypeArg<T>>::Type 传递给类型为 <TCon as WithTypeArg<T>>::Type 的参数，但它会将 <TCon as WithTypeArg<T>>::Type 传递给 TypeApp<TCon, T> 的特质参数。

请注意，在实现中，这意味着我们必须将所有 x 的出现替换为 x.into_val()，其中 into_val 是特质 Is 的一部分（在 TypeApp 的 where 子句中）。

基本上，这是这种方法的核心。我们只是对 Applicative 和 Monad 做类似的事情，但下面我会详细介绍遇到的一些细节和问题。

上面的类称为 Mappable，而实际上我在上面详细说明的它是库中称为 LinearFunctor 的，我现在也会谈谈这个。

库的结构。

目前，库中有 7 个主要特质

• Functor
• Lift
• Applicative
• Monad
• LinearFunctor
• LinearApplicative
• LinearMonad

Functor、Applicative 和 Monad基本上是从 Haskell 复制的，除了 Applicative 的 pure 函数被拆分为特质 Lift。所以 Lift 和 Applicative 扩展 Functor，而 Monad 扩展了 Lift 和 Applicative。

LinearFunctor/LinearApplicative/LinearMonad 是 Functor/Applicative/Monad 的 "按值" 版本。这些类型类消耗它们的参数。这可以是一个效率提升，因为它们不需要复制它们的参数，这也意味着它们可以定义在不是 Cloneable 的类型上。

// Implement this trait for LinearFunctor
pub trait LinearFunctor {
    fn lmap<TIn, TOut>(
        f: impl Fn(TIn) -> TOut,
        x: <Self as WithTypeArg<TIn>>::Type,
    ) -> <Self as WithTypeArg<TOut>>::Type
    where
        Self: WithTypeArg<TIn> + WithTypeArg<TOut>;
}

// Call this for lmap(f, x) syntax
pub fn lmap<TCon, TIn, TOut>(
    f: impl Fn(TIn) -> TOut,
    x: impl TypeApp<TCon, TIn>,
) -> <TCon as WithTypeArg<TOut>>::Type
where
    TCon: LinearFunctor + WithTypeArg<TIn> + WithTypeArg<TOut> + ?Sized,
{
    <TCon as LinearFunctor>::lmap(f, x.into_val())
}

// This is for x.lmapop(f) syntax
pub trait LMapExt {
    fn lmap<TCon, TIn, TOut>(self, x: impl TypeApp<TCon, TIn> + Sized) -> <TCon as WithTypeArg<TOut>>::Type
    where
        Self: Fn(TIn) -> TOut + Sized,
        TCon: LinearFunctor + WithTypeArg<TIn> + WithTypeArg<TOut>
    {
        lmap(self, x)
    }
}

impl<T> LMapExt for T {}

    fn lmap2<TIn, TMid, TOut, TCon>(
        f: impl Fn(TIn) -> TMid,
        g: impl Fn(TMid) -> TOut,
        x: impl TypeApp<TCon, TIn>,
    ) -> <TCon as WithTypeArg<TOut>>::Type
    where
        TCon: LinearFunctor + WithTypeArg<TIn> + WithTypeArg<TMid> + WithTypeArg<TOut>
    {
        lmap(g, lmap(f, x))
    }

pub trait Applicative: Functor + Lift {
    fn ap<TIn, TOut, TFunc>(
        f: &<Self as WithTypeArg<TFunc>>::Type,
        x: &<Self as WithTypeArg<TIn>>::Type,
    ) -> <Self as WithTypeArg<TOut>>::Type
    where
        Self: WithTypeArg<TFunc> + WithTypeArg<TIn> + WithTypeArg<TOut>,
        TFunc: Fn(&TIn) -> TOut,
    {
        <Self as Applicative>::lift2(|y1: &TFunc, y2: &TIn| y1(y2), f, x)
    }

    fn lift2<TIn1, TIn2, TOut, TFunc>(
        f: TFunc,
        x1: &<Self as WithTypeArg<TIn1>>::Type,
        x2: &<Self as WithTypeArg<TIn2>>::Type,
    ) -> <Self as WithTypeArg<TOut>>::Type
    where
        Self: WithTypeArg<TIn1> + WithTypeArg<TIn2> + WithTypeArg<TOut>,
        TFunc: Fn(&TIn1, &TIn2) -> TOut;
}

lift2(f, x, y) = f.fmap(x).ap(y)

lift2(f, x, y) = (|x| |y| f(x,y)).fmap(x).ap(y)

// lift(x)
pub fn lift<TCon, T>(x: T) -> <TCon as WithTypeArg<T>>::Type
where
    <TCon as WithTypeArg<T>>::Type : TypeApp<TCon, T>,
    TCon: Lift + WithTypeArg<T>,
{
    <TCon as Lift>::lift::<T>(x)
}


// lift_c(x)
pub fn lift_c<TCon, T, U>(x: U::Param) -> U
where
    T : Is<Type = U::Param>,
    U : TypeApp<TCon, T>,
    <TCon as WithTypeArg<T>>::Type : TypeApp<TCon, T>,
    TCon: Lift + WithTypeArg<T>,
{
    Is::from_val(lift::<TCon, T>(Is::from_val(x)))
}

x: Option<u32> = lift(5);

x: Option<u32> = lift_c(5);

let o1: Option<u32> = lift_c(5);
let o2: Option<u32> = lift_c(7);

let _do_result: Option<(u32, u32)> = mdo_c! {
    x =<< &o1;
    y =<< &o2;
    ret (Clone::clone(x), Clone::clone(y));
};

    fn monadic_pair<TCon, T, TArg>(x: &TArg, y: &TArg) -> <TCon as WithTypeArg<(T, T)>>::Type
    where
        TCon: Monad + WithTypeArg<T> + WithTypeArg<(T, T)>,
        TArg: TypeApp<TCon, T>,
        T: Clone,
    {
        mdo! {
            x_val =<< x;
            y_val =<< y;
            ret<TCon> (x_val.clone(), y_val.clone());
        }
    }

trait TypeCon<TCon> where TCon : forall U. WithTypeArg<U>