Stack overflow is your friend, you can even vote for the best anwser !
Le 7 déc. 2013 17:43, "David Piepgrass" <[email protected]> a écrit :
> (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 <[email protected]>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
> [email protected]
> https://mail.mozilla.org/listinfo/rust-dev
>
>
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
