Rust 中 GAT 和高階類型

Rust 在類型系統級別上與Haskell,Scala有許多相似之處。

兩者都有類型 (type)，泛型類型 (generic types), 關聯類型 (associated types) 和特質 / 類型類 (traits/type classes)(基本上是等效的)。

但是，Haskell有Rust缺乏的一個特性: 高階類型 (Higher Kinded Types), 也就是通常說的HKTs。

這不是Rust故意不添加，也不是Rust應該填補的一些差距。其實這是Rust的一個有意的設計。

結果就是，到沒有GATs出現時，某些代碼無法真正在 Rust 中實現。

以Haskell中的Functor爲例。Functor其實是對類型上實現的map的一個更加抽象的實現, 不關心具體類型的一個接口。

比如，在Scala中，要實現一個map的Functor是這樣的:

import scala.language.higherKinds

trait Functor[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
}

如果你使用過Scala的集合 api，這看起來應該非常相似。所有集合都可以使用 map。

List(1, 2, 3).map(_ + 1)
// List(2, 3, 4)

你可能要問，什麼是高階類型啊. 你可以先理解爲: 高階類型是類型的類型。這是什麼意思呢? 我以Scala裏面的代碼來說明一下。

scala> trait MyList[A] {
  def head: A
  def tail: MyList[A]
}

然後用:k命令看下是什麼類型:

scala> :k -v MyList
MyList's kind is F[A]
* -> *
This is a type constructor: a 1st-order-kinded type.

MyList[String]類型是一個一階類型 (1st-order-kinded type); 任何MyList的類型都是由A參數化的，可以將MyList看作是一個類型函數，如A => MyList[A]，因此給定一個類型A，我們可以創建一個新的類型MyList[A]。如果MyList是一階類型，那麼什麼是類型化類型呢? 其實想想, 什麼是高階函數啊? 它不就是一個接受函數然後返回另外另一個函數的函數。同理可得，什麼是高階類型呢? 它是由另一個類型參數化的類型。我再寫一個簡單的例子。

scala> trait Foo[F[_]]:k -v Foo
Foo's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

這裏的Foo就是一個高階類型。它是一個類型構造函數，參數也是一個類型構造函數。爲了說清楚這點，我再寫一個例子. 我寫一個trait，裏面有一個leftFold的方法。

scala> trait Foldable[F[_]] {
     |     def leftFold[A,B](ob: F[A])(zero: B)(fn: (B,A) => B): B
     | }

然後呢，我再實現一個listFoldable, 這是最常見的吧。

scala> implicit val listFoldable: Foldable[List] = new Foldable[List] {
     |   def leftFold[A, B](ob: List[A])(zero: B)(fn: (B, A) => B): B = {
     |     ob.foldLeft(zero)(fn)
     |   }
     | }

上面我定義了一個適用於任何List類型的Foldable對象。leftFold方法將取A並使用A構造List[A]。

一種更好的寫法:

scala> import scala.language.implicitConversions
import scala.language.implicitConversions

scala> implicit class ListFoldableOpt[A](list: List[A])(implicit fold: Foldable[List]) {
     |     def leftFold[B](zero: B)(fn: (B, A) => B): B =
     |         fold.leftFold(list)(zero)(fn)
     | }
     
scala> List(1, 2, 3).leftFold(0)(_ + _) // 6

這裏先收一下，回到Rust中。

Rust中的很多不同結構都實現了map函數，比如: Option, Result, Iterator, and Future.

但是, 在 Rust 裏面，還不能編寫可以給多種類型實現的通用Functortrait, 就像我剛纔上面寫的trait Functor[F[_]]。通常呢在 Rust 裏面是單個類型單獨去實現map。例如，我這裏自己寫了一個MyOption和MyResult枚舉類, 並實現了map方法.

#[derive(Debug, PartialEq)]
    enum MyOption<A> {
    Some(A),
    None,
}

impl<A> MyOption<A> {
    fn map<F: FnOnce(A) -> B, B>(self, f: F) -> MyOption<B> {
        match self {
            MyOption::Some(a) => MyOption::Some(f(a)),
            MyOption::None => MyOption::None,
        }
    }
}

#[test]
fn test_option_map() {
    assert_eq!(MyOption::Some(5).map(|x| x + 1), MyOption::Some(6));
    assert_eq!(MyOption::None.map(|x: i32| x + 1), MyOption::None);
}

#[derive(Debug, PartialEq)]
enum MyResult<A, E> {
    Ok(A),
    Err(E),
}

impl<A, E> MyResult<A, E> {
    fn map<F: FnOnce(A) -> B, B>(self, f: F) -> MyResult<B, E> {
        match self {
            MyResult::Ok(a) => MyResult::Ok(f(a)),
            MyResult::Err(e) => MyResult::Err(e),
        }
    }
}

#[test]
fn test_result_map() {
    assert_eq!(MyResult::Ok(5).map(|x| x + 1), MyResult::Ok::<i32, ()>(6));
    assert_eq!(MyResult::Err("hello").map(|x: i32| x + 1), MyResult::Err("hello"));
}

上面的幾個例子都是直接在自己的結構中定義的 map 方法。如果沒有 GATs, 就不可能將map定義爲一個trait的方法。這是爲什麼呢? 下面是一個在 Rust 裏面簡單的Functortrait 實現，以及 Option 的實現.

trait NaiveFunctor {
    type T;
    fn map<F>(self, f: F) -> Self
        where
            F: FnMut(Self::T) -> Self::T;
}

impl<A> NaiveFunctor for Option<A> {
    type T = A;
    fn map<F: FnMut(A) -> A>(self, mut f: F) -> Option<A> {
        match self {
            Some(a) => Some(f(a)),
            None => None,
        }
    }
}

在上面的trait定義中，先給NaiveFunctor內部的值定義了一個關聯類型 T。給Option<A>impl 這個 trait，T=A。這就是問題所在。 Rust 將 T 硬編碼爲一種類型 A，因爲通常在 map 函數中，希望返回的類型是B，但在之前版本穩定的 Rust 中，沒有辦法說 " 我想要一個既能與NaiveFunctor關聯的類型，又要求這個類型和關聯類型有一點不一樣。

這就是泛型關聯類型發揮作用的地方了。

多態 Functor 的實現

爲了得到一個多態Functor. 我想要的是："我的類型最終應該是我在其中包裹的類型". 例如，對於Option，我想說的是 " 如果我有一個Option<A>，那麼它肯定包含一個A類型, 但如果它包含一個B類型，它將是Option<B>"

這裏就需要使用泛型關聯類型.

trait Functor {
    type Unwrapped;
    type Wrapped<B>: Functor;
    fn map<F, B>(self, f: F) -> Self::Wrapped<B>
        where
            F: FnMut(Self::Unwrapped) -> B;
}

說明下上面的寫法:

每個Functor都有一個關聯的Unwrapped類型.
還有另一個關聯類型Wrapped<B>，它與Self類似，但有一個不同的包裝值
和前面例子一樣, map接受兩個參數的一個是:self和一個函數
函數形參將從當前關聯的Unwrapped值映射到一個新的類型B
map 的輸出是一個Wrapped<B>

有點抽象。具體點現在看下Option類型是什麼樣子的

impl<A> Functor for Option<A> {
    type Unwrapped = A;
    type Wrapped<B> = Option<B>;

    fn map<F:FnMut(A) -> B, B>(self, mut f: F) -> Option<B> where F: FnMut(A) -> B {
        match self {
            Some(x) => Some(f(x)),
            None => None,
        }
    }
}

#[test]
fn test_option_map() {
    assert_eq!(Some(5).map(|x| x + 1), Some(6));
    assert_eq!(None.map(|x: i32| x + 1), None);
}

編譯通過，非常優雅。

類型類

在Haskell和Scala中，其實是不需要這種泛型關聯類型的。事實上，Haskell中Functors不使用任何關聯類型。Haskell中Functor的類型類遠遠早於其他語言中關聯類型的出現。爲了進行比較，先看看它是什麼樣子。

class Functor f where
    map :: (a -> b) -> f a -> f b
    
instance Functor Option where
    map f option =
        case option of
            Some x -> Some (f x)
            None -> None

trait Functor[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
}

把它轉換成 Rust 就是如下:

trait HktFunctor {
    fn map<A, B, F: FnMut(A) -> B>(self: Self<A>, f: F) -> Self<B>;
}

impl HktFunctor for Option {
    fn map<A,B, F: FnMut(A) -> B>(self: Option<A>, f: F) -> Option<B> {
        match self {
            Some(a) => Some(f(a)),
            None => None,
        }
    }
}

但是上面的代碼是編譯不通過的。因爲我試圖給 Self 提供類型參數。但是在Rust中, 單獨一個Option不是一個類型. Option要成爲一個類型，必須有一個類型參數. 比如: Option<i32> 是一個類型. Option卻不是.

相反，在Haskell中，Maybe Int是kind type的一種類型。Maybe是類型構造函數，類型爲type -> type。但是出於創建類型類和實例的目的，可以將Maybe處理爲具有自己的類型。Haskell中的Functor作用於type->type。

這就是我所說的 "高階類型": 就是說我可以寫出擁有類型的類型 (Kind)。

Pointer 的實現

Haskell中有一個有爭議的類型類叫做Pointed。之所以有爭議的，是因爲它引入了一個類型類，但沒有與它相關的任何laws。我想在 Rust 中實現下Pointed。

什麼是 Pointed

Pointed的思想很簡單: 將一個值包裝成一個類似Functor的東西。比如：在Option的情況下，它就用Some包裝它。在Result中，它使用Ok。對於Vec，它是一個單值向量。與Functor不同，這裏是一個靜態方法，因爲我們沒有現有的Point值要改。讓我們看看它在 Rust 中的實現。

trait Pointed: Functor {
    fn wrap<T>(t: T) -> Self::Wrapped<T>;
}

impl<A> Pointed for Option<A> {
    fn wrap<T>(t: T) -> Self::Wrapped<T> {
        Some(t)
    }
}

這裏需要注意的是：我根本沒有在Option實現中使用A類型參數。

還有一點值得注意。調用 wrap 的結果返回的是Self::Wrapped<T>。關於Self::Wrapped<T>，到底是什麼? 從之前Functor的定義中，確切地知道一件事:Wrapped<T>必須是一個Functor的。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/96WpYXhiq29r40Zd_ImXAA

多態 Functor 的實現

類型類

Pointer 的實現

什麼是 Pointed

猜你喜歡