2 ms·
Let me try to explain GAT from a C++ programmer perspective: 'int' is a type. 'vector<int>' is also a type but 'vector' itself can be understood as a function
by gpderetta 4y ago
Let me try to explain GAT from a C++ programmer perspective:
'int' is a type.
'vector<int>' is also a type
but 'vector' itself can be understood as a function from type to type (for example, invoking vector with an int produces vector<int>)
Now let's say you want a function that given a type produces a vector of pairs of that type. In C++ you could do:
template<class T>
struct pair_vector : vector<pair<T, T> > {};
But using inheritance for this is not great, the result of pair_vector<int> is really not a vector<pair<int,int> >. You can use an associated type:
template<class T>
struct pair_vector { using result = vector<pair<T, T>>; };
now 'pair_vector<int>::result' is exactly 'vector<pair<T,T> >' [1].
So these are first order type functions. Let's say you want higher order type functions, i.e. functions that take other type functions as parameters or return them.
For example let's say you want a to build a pair<X,Y> piece wise: you want a function pair_1st that given a type X returns another function that takes a type Y and finally returns a pair<X,Y>:
template<class X>
struct pair_1st {
template<class Y>
struct apply { using result = pair<X, Y>; };
};
So: 'pair_1st<int>::apply<double>::result' is 'pair<int, double>';
'pair_1st' is an higher order function from type => (to a function form type => type).
Apply here is an associated type, (like result before), but is generic, hence an associated generic type.
So, what if we also want to abstract over pair in 'pair_1st', i.e. an higher order function that takes two parameters, the first a function from type => to type, and the second a type:
template<template<class T1,class T2> F, class X> struct bind_1st {
template<class Y>
struct apply { using result = F<X, Y>; }
};
Now 'bind_1st<pair, int>::apply<double>::result' is again pair<int, double>;
I think that rust doesn't allow higher order (i.e. template template) parameters, but that's not a big problem:
template<template<class F, class X> struct bind_1st {
template<class Y>
struct apply { using result = F::apply<X, Y>::result; } [2]
};
struct pair_fn {
template<class X, class Y> struct apply { using result = pair<X, Y>; };
};
By lifting pair into into a pair_fn class with a GAT we can solve the issue: bind_1st<pair_fn, int>::apply<double>::result is again the same as pair<int, double>. In fact in C++ for a long time, before variadic templates, even if template template parameters were available from the beginning, GATs were the preferred way to encode higher order type functions.
The big difference between rust and C++ of course is that the type level functions in C++ are untyped other than maybe being able to specify the arity, while rust has a proper type system for generics, which I assume make all of this more complicated to implement from a compiler point of view.
Now why would you want all this nonsense outside of hardcore type level programming? Well, there is a continuum from simply writing a generic class to actual metaprogramming, so even if you do not want to do the latter, you might end up using on some of this stuff even for relatively simple generics.
[1] we can use template using to hide ::result, but that's a c++ quirk which is not important in the grand scheme of things.
[2] template typename noise removed for sanity