Re: [rust-dev] Higher-Kinded Types vs C++ Combos
(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 { templatetypename T typedef listT 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.comwrote: 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 { collectionint integers; collectionfloat floats; }; So then you can write Numbersvector for a structure that contains vectorT collections, and Numberslist for a structure that contains listT collections. EXCEPT that it doesn't actually work, because vectorT 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 { templatetypename T struct collection { typedef vectorT type; }; }; struct ListTrait { templatetypename T struct collection { typedef listT type; }; }; templatetypename Traits struct Numbers { Traits::collectionint::type integers; Traits::collectionfloat::type floats; }; // Use NumbersVectorTrait for vectorT, NumbersListTrait for listT. This is clunkier, but it would have been a bit simpler if C++ supported templatized typedefs: struct VectorTrait { templatetypename T typedef vectorT collection; }; struct ListTrait { templatetypename T typedef vectorT collection; }; templatetypename Traits struct Numbers { Traits::collectionint
Re: [rust-dev] Higher-Kinded Types vs C++ Combos
Stack overflow is your friend, you can even vote for the best anwser ! Le 7 déc. 2013 17:43, David Piepgrass qwertie...@gmail.com 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 { templatetypename T typedef listT 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.comwrote: 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 { collectionint integers; collectionfloat floats; }; So then you can write Numbersvector for a structure that contains vectorT collections, and Numberslist for a structure that contains listT collections. EXCEPT that it doesn't actually work, because vectorT 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 { templatetypename T struct collection { typedef vectorT type; }; }; struct ListTrait { templatetypename T struct collection { typedef listT type; }; }; templatetypename Traits struct Numbers { Traits::collectionint::type integers; Traits::collectionfloat::type floats; }; // Use NumbersVectorTrait for vectorT, NumbersListTrait for listT. This is clunkier, but it would have been a bit simpler if C++ supported templatized typedefs: struct VectorTrait {
Re: [rust-dev] Higher-Kinded Types vs C++ Combos
Short version: yes, higher-kinded types and template template parameters are the same thing. (`templatetypename class` is just one particular higher kind; there's also `templatetemplatetypename class class` and so on, and varying the number of parameters, etc., which you probably know.) Longer version hopefully upcoming if/when I manage to digest the rest of it. On Sat, Dec 7, 2013 at 8:10 AM, David Piepgrass qwertie...@gmail.comwrote: 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 { collectionint integers; collectionfloat floats; }; So then you can write Numbersvector for a structure that contains vectorT collections, and Numberslist for a structure that contains listT collections. EXCEPT that it doesn't actually work, because vectorT 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 { templatetypename T struct collection { typedef vectorT type; }; }; struct ListTrait { templatetypename T struct collection { typedef listT type; }; }; templatetypename Traits struct Numbers { Traits::collectionint::type integers; Traits::collectionfloat::type floats; }; // Use NumbersVectorTrait for vectorT, NumbersListTrait for listT. This is clunkier, but it would have been a bit simpler if C++ supported templatized typedefs: struct VectorTrait { templatetypename T typedef vectorT collection; }; struct ListTrait { templatetypename T typedef vectorT collection; }; templatetypename Traits struct Numbers { Traits::collectionint integers; Traits::collectionfloat floats; }; // Now write NumbersVectorTrait instead of Numbersvector, // NumbersListTrait instead of Numberslist. 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 ConcreteATraits A; typedef ConcreteBTraits B; typedef ConcreteCTraits C; }; templatetypename Combo class ConcreteA { Combo::B* b; ... }; templatetypename Combo class ConcreteB { Combo::C* c; ... }; templatetypename Combo class ConcreteC { Combo::A* b; ... }; Here I've created a network of types (ConcreteAMyCombo, ConcreteBMyCombo, and ConcreteCMyCombo) 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
Re: [rust-dev] Higher-Kinded Types vs C++ Combos
In all these cases with typedefs, you're still implicitly relying on higher-kinded types, along with what are usually referred to as associated types: http://smallcultfollowing.com/babysteps/blog/2013/04/02/associated-items/ http://smallcultfollowing.com/babysteps/blog/2013/04/03/associated-items-continued/ Kinds are basically the types of types. In the normal case there's two varieties: - The base kind, which is the kind of what you normally think of as types, i.e. things which can be the type of values. In C++ this is called typename/class (in Haskell: *). - The kind of functions from types of one kind to types of another (potentially the same) kind; in other words, the kind of types parameterized over type arguments (of varying kind). The simplest case is the kind of functions from the base kind to the base kind, in C++ templatetypename class (in Haskell: * - *). Then you can iterate the second rule however you like for an infinite regress of different kinds. In all of these examples you're using an implicit protocol (type of a particular kind with a particular name as a member) to encode associated types. The associated types themselves are of higher kinds. In the Numbers example, the type parameter itself is the base kind, but has an associated type with a templatized (function) kind, which is what you're actually using. In this case you could just as easily skip the middleman and pass around the higher-kinded type directly, but associated types also give you the ability to branch over the input type, which higher-kinded types by themselves do not. (This is what happens, for example, when strings declare that their element type is a character, instead of being parameterized over an element type.) Basically, this form of typedefs already implies HKT, and if we were to add HKT, there would be no reason to restrict them to only being associated types. On Sat, Dec 7, 2013 at 9:05 PM, Gábor Lehel illiss...@gmail.com wrote: Short version: yes, higher-kinded types and template template parameters are the same thing. (`templatetypename class` is just one particular higher kind; there's also `templatetemplatetypename class class` and so on, and varying the number of parameters, etc., which you probably know.) Longer version hopefully upcoming if/when I manage to digest the rest of it. On Sat, Dec 7, 2013 at 8:10 AM, David Piepgrass qwertie...@gmail.comwrote: 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 { collectionint integers; collectionfloat floats; }; So then you can write Numbersvector for a structure that contains vectorT collections, and Numberslist for a structure that contains listT collections. EXCEPT that it doesn't actually work, because vectorT 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 { templatetypename T struct collection { typedef vectorT type; }; }; struct ListTrait { templatetypename T struct collection { typedef listT type; }; }; templatetypename Traits struct Numbers { Traits::collectionint::type integers; Traits::collectionfloat::type floats; }; // Use NumbersVectorTrait for vectorT, NumbersListTrait for listT. This is clunkier, but it would have been a bit simpler if C++ supported templatized typedefs: struct VectorTrait { templatetypename T typedef vectorT collection; }; struct ListTrait { templatetypename T typedef vectorT collection; }; templatetypename Traits struct Numbers { Traits::collectionint integers; Traits::collectionfloat floats; }; // Now write NumbersVectorTrait instead of Numbersvector, // NumbersListTrait instead of Numberslist. 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
[rust-dev] Higher-Kinded Types vs C++ Combos
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 { collectionint integers; collectionfloat floats; }; So then you can write Numbersvector for a structure that contains vectorT collections, and Numberslist for a structure that contains listT collections. EXCEPT that it doesn't actually work, because vectorT 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 { templatetypename T struct collection { typedef vectorT type; }; }; struct ListTrait { templatetypename T struct collection { typedef listT type; }; }; templatetypename Traits struct Numbers { Traits::collectionint::type integers; Traits::collectionfloat::type floats; }; // Use NumbersVectorTrait for vectorT, NumbersListTrait for listT. This is clunkier, but it would have been a bit simpler if C++ supported templatized typedefs: struct VectorTrait { templatetypename T typedef vectorT collection; }; struct ListTrait { templatetypename T typedef vectorT collection; }; templatetypename Traits struct Numbers { Traits::collectionint integers; Traits::collectionfloat floats; }; // Now write NumbersVectorTrait instead of Numbersvector, // NumbersListTrait instead of Numberslist. 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 ConcreteATraits A; typedef ConcreteBTraits B; typedef ConcreteCTraits C; }; templatetypename Combo class ConcreteA { Combo::B* b; ... }; templatetypename Combo class ConcreteB { Combo::C* c; ... }; templatetypename Combo class ConcreteC { Combo::A* b; ... }; Here I've created a network of types (ConcreteAMyCombo, ConcreteBMyCombo, and ConcreteCMyCombo) 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? ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Higher-Kinded Types vs C++ Combos
Of course this leads (assuming we had a `Collection` trait) to the horrendously ugly `Numbers::i32, ~[i32], f32, ~[f32](...)` if you wanted to be explicit. But hopefully your code would be such that Rust could infer the bounds. This will be alleviated in the future by associated items, but that will probably be post 1.0. (I might be getting a little off-topic here) ~Brendan On 7 Dec 2013, at 5:27 pm, Brendan Zabarauskas bjz...@yahoo.com.au wrote: I’m not sure I understand everything in your post, but this is how I’d write you first C++ example: struct NumbersIV, FV { priv iv: IV,// priv so the struct can only be constructed in this module priv fv: FV, } implI: Int, IV: CollectionI, F: Float, FV: CollectionF NumbersIV, FV { pub fn new(iv: IV, fv: FV) - NumbersIV, FV { Numbers { iv: iv, fv: fv } } } You can also write type aliases with type parameters, but I don’t think you can enforce trait bounds on them afaik: type AT = (T, int); ~Brendan On 7 Dec 2013, at 5:10 pm, 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 { collectionint integers; collectionfloat floats; }; So then you can write Numbersvector for a structure that contains vectorT collections, and Numberslist for a structure that contains listT collections. EXCEPT that it doesn't actually work, because vectorT 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 { templatetypename T struct collection { typedef vectorT type; }; }; struct ListTrait { templatetypename T struct collection { typedef listT type; }; }; templatetypename Traits struct Numbers { Traits::collectionint::type integers; Traits::collectionfloat::type floats; }; // Use NumbersVectorTrait for vectorT, NumbersListTrait for listT. This is clunkier, but it would have been a bit simpler if C++ supported templatized typedefs: struct VectorTrait { templatetypename T typedef vectorT collection; }; struct ListTrait { templatetypename T typedef vectorT collection; }; templatetypename Traits struct Numbers { Traits::collectionint integers; Traits::collectionfloat floats; }; // Now write NumbersVectorTrait instead of Numbersvector, // NumbersListTrait instead of Numberslist. 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 ConcreteATraits A; typedef ConcreteBTraits B; typedef ConcreteCTraits C; }; templatetypename Combo class ConcreteA { Combo::B* b; ... }; templatetypename Combo class ConcreteB { Combo::C* c; ... }; templatetypename Combo class ConcreteC { Combo::A* b; ... }; Here I've created a network of types (ConcreteAMyCombo, ConcreteBMyCombo, and ConcreteCMyCombo) 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