(Another big reason I like forums over mailing lists, which I forgot to
mention in that other thread, is that I can fix my mistakes!) Typo
correction:
struct ListTrait
{
template<typename T> typedef list<T> collection;
};
And I'd rephrase my third question:
3. If Rust had C++-style typedefs, would it make sense to argue that "we
don't need Higher-Kinded Types, we can just use typedefs for everything"?
In case people are finding the Combo concept hard to follow, I will offer
GiST (http://en.wikipedia.org/wiki/GiST) as a concrete example. A GiST has
a few different parts, each of which can be swapped out to produce
different kinds of trees. When I tried to implement the GiST in C#, I found
that I wanted 8 type parameters on the GiST base class:
- The derived tree type
- The internal node type
- The leaf node type
- The "compressed" left entry type
- The "uncompressed" leaf entry type
- The "compressed" internal entry type
- The "uncompressed" internal entry type
- The key type (type of data stored in an entry)
This, of course, is utterly impractical when they have to be listed
repeatedly, every time the base class is mentioned. I figured out how to
whittle it down to one parameter on the base class and two elsewhere, but I
had to restructure the code in some unnatural ways, so the readability of
the code was substantially harmed, and there was some performance cost as
well (some interfaces, some virtual methods, more casts.)
Even with one or two type parameters, the names of things were still
unweildy because often the concrete type parameters were themselves
parameterized.
Of course, type parameters are not the only way to do a GiST. It can also
be done by defining everything in terms of interfaces (or in Rust, trait
objects). But this implies that when the different parts of the code
interact, they must use dynamic dispatch. Even worse, although the entries
(leaf/internal, compressed/uncompressed) are small implicitly-copyable data
types (let's say 8 - 32 bytes typically, though I don't have the code
handy), most of the code will be unaware how large or small each entry is,
so the entries would (in C# at least) have to be stored on the heap, rather
than passed around directly as structs (I'm not sure what you'd do in Rust).
Thus, if you want to implement a GiST in C# you get either hard-to-follow
code with sub-optimal performance, or straightforward code with terrible
performance. The third alternative, of course, is to not implement a GiST,
but implement each kind of tree (B+ tree, R-tree, ...) separately. This
requires code duplication and repeated design work, the elimination of
which was the reason GiSTs were invented in the first place.
In Rust, I assume you could use macros to overcome some of the problems
that make a GiST difficult to do in C#. However, I am thinking that if
"typedef" is in some ways a more powerful concept than HKT, arguably Rust
should support them first or investigate whether they can be generalized to
do what HKTs were meant to do.
On Sat, Dec 7, 2013 at 12:10 AM, David Piepgrass <qwertie...@gmail.com>wrote:
> Rust newb here. I have theoretical questions.
>
> Recently I noticed that Higher-Kinded Types (HKTs) have been mentioned on
> the mailing list a lot, but I had no idea what a HKT was, or what it might
> be good for. After reading about them a little, they reminded me of C++'s
> "template template parameters". In C++ you can almost write something like
> this:
>
> template <template <typename> class collection>
> struct Numbers {
> collection<int> integers;
> collection<float> floats;
> };
>
> So then you can write Numbers<vector> for a structure that contains
> vector<T> collections, and Numbers<list> for a structure that contains
> list<T> collections. EXCEPT that it doesn't actually work, because
> vector<T> has two template parameters (the second one, the allocator, is
> normally left at its default). Let's ignore that, though.
>
> So that brings me to my first question: is this what "higher-kinded types"
> means? What is the difference, if any, between HKT and C++ "template
> templates"?
>
> However, as a C++ developer I never actually used a "template template"
> parameter because I didn't know they existed for a long time. So instead I
> would have written this, which has the same end-result:
>
> struct VectorTrait
> {
> template<typename T>
> struct collection { typedef vector<T> type; };
> };
> struct ListTrait
> {
> template<typename T>
> struct collection { typedef list<T> type; };
> };
>
> template<typename Traits>
> struct Numbers
> {
> Traits::collection<int>::type integers;
> Traits::collection<float>::type floats;
> };
> // Use Numbers<VectorTrait> for vector<T>, Numbers<ListTrait> for list<T>.
>
> This is clunkier, but it would have been a bit simpler if C++ supported
> templatized typedefs:
>
> struct VectorTrait
> {
> template<typename T> typedef vector<T> collection;
> };
> struct ListTrait
> {
> template<typename T> typedef vector<T> collection;
> };
>
> template<typename Traits>
> struct Numbers
> {
> Traits::collection<int> integers;
> Traits::collection<float> floats;
> };
> // Now write Numbers<VectorTrait> instead of Numbers<vector>,
> // Numbers<ListTrait> instead of Numbers<list>.
>
> I have found that because of the existence of typedef, "template template"
> parameters are never actually necessary; so far, I've never seen a
> situation where the typedef-based solution wasn't almost as good. Also, I
> have found that "trait" types filled with typedefs seem to be a more
> general thing than "template template"; they allow you to do things that
> would be very difficult or impossible without them. For example you can use
> typedefs-in-a-struct to create circular references among types that don't
> "know" about each other:
>
> // I call this a "Combo"; I don't know if the technique has a standard name
> struct MyCombo {
> typedef ConcreteA<Traits> A;
> typedef ConcreteB<Traits> B;
> typedef ConcreteC<Traits> C;
> };
> template<typename Combo>
> class ConcreteA { Combo::B* b; ... };
> template<typename Combo>
> class ConcreteB { Combo::C* c; ... };
> template<typename Combo>
> class ConcreteC { Combo::A* b; ... };
>
> Here I've created a network of types (ConcreteA<MyCombo>,
> ConcreteB<MyCombo>, and ConcreteC<MyCombo>) that are linked together
> through the "Combo" type MyCombo, so the types can all use each other, but
> none of the types refer to each other directly. This design allows you to
> freely swap in different implementations of A, B, and C; it has similar
> advantages to "dependency injection" or "inversion of control" in languages
> like Java and C#, except that the linkages are all defined statically at
> compile-time, so no dynamic dispatch is required.
>
> Without the ability to define "typedefs", this approach is not possible at
> all if there is a cyclic relationship. Also, if the combo declares more
> than three types, it becomes impractical to specify all those types on the
> classes directly as type parameters.
>
> In C# I learned that this quickly becomes a major problem if you need to
> parameterize on more than one or two types. I tried to do "generic" math
> (which requires at least two type parameters due to the under-designed
> standard libraries) and I also implemented a GiST data structure (see
> http://en.wikipedia.org/wiki/GiST), and found out that the lack of any
> analog to C++ typedef makes both of those tasks very clumsy, while also
> making the code hard to read, because you end up with a rats' nest of type
> parameters (or if you omit (otherwise necessary) type parameters, you might
> use lots of casts instead.)
>
> So I guess that leads me to two more questions.
>
> 2. Does Rust have a "typedef" equivalent that can be used in this way?
> 3. Does it make sense to just suggest "just use typedefs instead of
> Higher-Kinded Types"?
>
>
--
- David
http://qism.blogspot.com
_______________________________________________
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
