第十三號艦隊
0%

GAT equivalence in C++

Posted on Edited on

一開始看到GAT也不知道在幹嘛，是看到Could someone explain the GATs like I was 5?才有感覺]
最簡單的範例，現在有一個struct

1
struct Foo { bar: Rc<String>, }

假設你要同時支援 Rc和’Arc的版本
該怎麼做

Naive solution

1
2
struct FooRc { bar: Rc<String>, }
struct FooArc { bar: Arc<String>, }

不過這當然沒什麼好說的

Macro solution

理論上辦得到，不過沒什麼優點

GAT Solution

我希望能寫成這樣

1
struct Foo<P: Pointer> { bar: P<String>, }

這樣是編譯不會過的，有了GAT之後，可以寫成這樣

1
2
3
4
5
6
7
trait PointerFamily { type Pointer<T>; }
struct RcFamily;  // Just a marker type; could also use e.g. an empty enum 
struct ArcFamily; // Just a marker type; could also use e.g. an empty enum 
impl PointerFamily for RcFamily { type Pointer<T> = Rc<T>; }
impl PointerFamily for ArcFamily { type Pointer<T> = Arc<T>; }

struct Foo<P: PointerFamily> { bar: P::Pointer<String>, }

C++ Solution

不過用C++對我來說反而更好理解，就是用nested template來做
首先是等價的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <typename T>
struct Rc {};
template <typename T>
struct Arc {};

struct RcFamily {
    template <typename T>
    using type = Rc<T>;
};

struct ArcFamily {
    template <typename T>
    using type = Arc<T>;
};

template <typename T>
struct PointerFamily {
    template <typename U>
    using type = T::template type<U>;
};

template <typename T>
struct Foo {
    typename PointerFamily<T>::template type<std::string> bar;
};

不過對於這問題，還有更簡單的方法
用template template parameter即可

1
2
3
4
5
6
7
8
9
template <typename T>
struct Rc {};
template <typename T>
struct Arc {};

template <template <typename> class T>
struct Foo {
    T<std::string> bar;
};

More complicated example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
trait Mappable {
    type Item;
    type Result<U>;
    fn map<U, P: FnMut(Self::Item) -> U>(self, f: P) -> Self::Result<U>;
}

impl<T> Mappable for Option<T> {
    type Item = T;
    type Result<U> = Option<U>;
    fn map<U, P: FnMut(Self::Item) -> U>(self, f: P) -> Option<U> {
        self.map(f)
    }
}

impl<T, E> Mappable for Result<T, E> {
    type Item = T;
    type Result<U> = Result<U, E>;
    fn map<U, P: FnMut(Self::Item) -> U>(self, f: P) -> Result<U, E> {
        self.map(f)
    }
}

等價的C++版本大概是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <class T>
struct Option {
    // Option implementation...
    // The "GAT":

    template <class U>
    using MapResult = Option<U>;
    template <class U, class F>

    Option<U> map(F f) {
        // Apply f to the contents of `this`
    }
};

template <class T>
concept Mappable = requires {
    typename T::template MapResult<int>;
};

template <Mappable T>
typename T::template MapResult<int> zero_to_42(T t) {
    return t.template map<int>([](int x) {
        return x == 0 ? 42 : 0 ;
    });
}