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
