www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Transforming a range back to the original type?

reply Jacob Carlborg <doob me.com> writes:
Is there a general function for transforming a range back to the 
original type? If not, would it be possible to create one?

-- 
/Jacob Carlborg
May 02 2012
next sibling parent reply Matt Soucy <msoucy csh.rit.edu> writes:
On 05/02/2012 05:01 PM, Jacob Carlborg wrote:
 Is there a general function for transforming a range back to the
 original type? If not, would it be possible to create one?

I believe std.array's array function does what you want. -Matt
May 02 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-05-02 23:07, Matt Soucy wrote:
 On 05/02/2012 05:01 PM, Jacob Carlborg wrote:
 Is there a general function for transforming a range back to the
 original type? If not, would it be possible to create one?

I believe std.array's array function does what you want. -Matt

I was thinking of a generic function that works for all types of collections and not arrays. -- /Jacob Carlborg
May 03 2012
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, May 02, 2012 23:01:21 Jacob Carlborg wrote:
 Is there a general function for transforming a range back to the
 original type? If not, would it be possible to create one?

You mean that if you have something like auto range = getRangeFromSomewhere(); auto newRange = find(filter!func(range), value); you want to transform newRange back to the same type as range? I don't believe that that's possible in the general case. For example, take Array!int a = getArrayFromSomewhere(0; auto range = a[]; auto newRange = find(filter!"a < 7"(range), 2); The type of a[] is specific to Array!int, cannot be created externally from it, and is tightly coupled with the container. What if the container held the values [1, 7, 2, 9, 42, 0, -2, 4]? newRange would end up having [2 , 0, -2 , 4], which doesn't correspond to any range of elements in the Array. So, how could you convert newRange to the same type as range? The best that you could do as far as I can tell would be to create a new Array!int, put those elements in it, and slice the container. So, I don't see how you could really take an arbitrary range and convert it back to its original type. With a very specific set of types, you might be able to (e.g. take([1, 2, 4, 9], 3) could be converted back to int[] easily enough), but with all of the wrapping that goes on with ranges, even determining what type of range is being wrapped by another can't be done generically AFAIK, let alone getting the whole chain down to the original range, let alone somehow converting the wrapped range back to that type. Take remove in std.container, for example. It will only take the container's range type or the result of take on the container's range type - and it had to special case take. And removing a range from a container would be classic example of where you need the original range type rather than a wrapper. - Jonathan M Davis
May 02 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-05-02 23:40, Jonathan M Davis wrote:
 On Wednesday, May 02, 2012 23:01:21 Jacob Carlborg wrote:
 Is there a general function for transforming a range back to the
 original type? If not, would it be possible to create one?

You mean that if you have something like auto range = getRangeFromSomewhere(); auto newRange = find(filter!func(range), value); you want to transform newRange back to the same type as range?

No, I want to transform newRange back to a collection, the same type as the original collection. I was thinking something like this: Collection c = new Collection(); c = c.filter!(x => x < 3).toCollection(); -- /Jacob Carlborg
May 03 2012
next sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-05-04 18:32, Jakob Ovrum wrote:

 After a quick look over the thread again, I still don't see any real
 examples of use cases from Jacob (I admit I could still be missing it...
 somewhere...).

I can't recall I ever had a use case where I wanted to do some operation on a collection and then transforming it to another type of collection. I just want to perform the operation, then get back a collection of the same type: int[] a = [3, 4, 5, 6 ,7]; a = a.filter!(x => x < 6); Since that's not possible with the way ranges are designed I was thinking if it at least would be possible to have a generic interface to get the a collection (of the same type) out of the range. -- /Jacob Carlborg
May 04 2012
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-05-04 22:05, Jakob Ovrum wrote:
 On Friday, 4 May 2012 at 19:17:13 UTC, Steven Schveighoffer wrote:
 This one:

 Collection c = new Collection();
 c = c.filter!(x => x < 3).toCollection();

 filter isn't a property of c, it's a range-producing function. So I
 only have to define filter once, as a range accepting, range producing
 function. And any container type, as long as it can produce a range,
 can use this as a pseudo method (via UFCS) to make a filtered copy of
 itself.

 -Steve

That's not a real example, that's pretty much the same example I provided below the part you quoted.

Real world example: https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/Type.d#L52 I was going to use "until" at row 59, but I couldn't figure out how to transform the range back to a string. -- /Jacob Carlborg
May 04 2012
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Jacob Carlborg:
 Is there a general function for transforming a range back to 
 the original type? If not, would it be possible to create one?

The newly redesigned containers in Scala language are often able to do this, but this has required the use of a very advanced static type system, that is currently not in D (maybe there are ways to implement it with D templates, but it will require work to implement). Currently there is array.array() that turns the range into a dynamic array. Probably some types/data structures will have a way to turn a lazy range into one of them. Bye, bearophile
May 02 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-05-03 00:34, bearophile wrote:

 The newly redesigned containers in Scala language are often able to do
 this, but this has required the use of a very advanced static type
 system, that is currently not in D (maybe there are ways to implement it
 with D templates, but it will require work to implement).

I've heard of that. I've started to read a paper about how the collection API is implemented. -- /Jacob Carlborg
May 03 2012
prev sibling next sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Wed, 02 May 2012 23:01:21 +0200, Jacob Carlborg <doob me.com> wrote:

 Is there a general function for transforming a range back to the  
 original type? If not, would it be possible to create one?

In addition to std.array.array, as others have pointed out, there is also std.range.InputRangeObject.
May 03 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-05-03 09:43, Simen Kjaeraas wrote:

 In addition to std.array.array, as others have pointed out,
 there is also std.range.InputRangeObject.

I'm not sure if I understand what InputRangeObject does. But I don't think it does what I want. -- /Jacob Carlborg
May 03 2012
prev sibling next sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Thu, 03 May 2012 13:17:40 +0200, Jacob Carlborg <doob me.com> wrote:

 On 2012-05-03 09:43, Simen Kjaeraas wrote:

 In addition to std.array.array, as others have pointed out,
 there is also std.range.InputRangeObject.

I'm not sure if I understand what InputRangeObject does. But I don't think it does what I want.

It basically wraps a range in a class interface. This allows you to use InputRangeObject!T instead of T[]. I've never used it, so I'm not sure what it does or how it does it.
May 03 2012
prev sibling next sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
On 02/05/2012 22:01, Jacob Carlborg wrote:
 Is there a general function for transforming a range back to the original
type? If not,
 would it be possible to create one?

To sum it up, it can't be done in the general case. The range API doesn't know or care about the underlying data structure. That's half the point of it. The underlying data structure might not even exist. An example is a range used as a file stream, a random number generator or to lazily generate a mathematical sequence. Moreover, what would you want such a function to return if the range is: - a file stream with a cache - an array wrapper to loop infinitely through it? - a concatenation of ranges that may be of different types? Moreover, even if there were some "range with an underlying container" classification, it would be an extra burden on the writer of the range wrapper to implement this. If you want to generate a range that views a container in a certain way, and then construct a container of the original type (or indeed any type) from that range, then create the container and then use a foreach loop on the range (or a .save of it, if you want to keep the range afterwards) to put the data into the container. Stewart.
May 03 2012
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-05-04 01:11, Stewart Gordon wrote:

 To sum it up, it can't be done in the general case. The range API
 doesn't know or care about the underlying data structure. That's half
 the point of it. The underlying data structure might not even exist. An
 example is a range used as a file stream, a random number generator or
 to lazily generate a mathematical sequence.

Yeah, I know, I know. It's all good in theory but I never found a use for it in practice and in most cases it's just annoying.
 Moreover, what would you want such a function to return if the range is:
 - a file stream with a cache
 - an array wrapper to loop infinitely through it?
 - a concatenation of ranges that may be of different types?

I was mostly thinking when the range originated from a collection. Where it's actually possible to transfer the range back to the original collection type.
 Moreover, even if there were some "range with an underlying container"
 classification, it would be an extra burden on the writer of the range
 wrapper to implement this.

No, I was thinking that the developer of the collection would provide that. I mean, it's already possible to transform a range to an array, I'm sure it's possible to transform it to a list of some kind as well. Then we could have this for example: collA.range.toArray(); collB.range.toList(); What I was asking for was if there is, or could be, a generic interface for this. Something like: collA.range.toCollection(); collA.range.toCollection(); If "collA" is an array "toCollection" would transform the range to an array, just as std.array.array does. If "collB" is a list the range would be transformed back in to a list.
 If you want to generate a range that views a container in a certain way,
 and then construct a container of the original type (or indeed any type)
 from that range, then create the container and then use a foreach loop
 on the range (or a .save of it, if you want to keep the range
 afterwards) to put the data into the container.

 Stewart.

-- /Jacob Carlborg
May 03 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-05-04 09:01, Jonathan M Davis wrote:

 Something like that could probably only be done if every range in the
 potentially large chain of wrapped ranges provided a means of getting at what
 type the previous one in the chain was, and very few ranges - if any - do
 that.

 However, I'm not quite sure what toCollection would buy you. Why does it
 really matter what type of container the range comes from originally given
 that you have to create a new container to put the elements of the range into
 such a container? And if you're putting the elements of a range in a new
 container, you can pick whatever container type you'd like, and since it has
 no real connection to the original container, I don't see why it would matter
 whether it was the same type of container. All you really need is the
 equivalent of std.array.array for whatever container you want to construct,
 and the container's constructor should provide that.

It's just like with the whole range idea, providing a common interface for iterating over a collection (and some other stuff). Here the idea is to have a common interface to transform the range back to a collection. -- /Jacob Carlborg
May 04 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-05-04 11:38, Jonathan M Davis wrote:
 On Friday, May 04, 2012 11:20:58 Jacob Carlborg wrote:
 On 2012-05-04 09:01, Jonathan M Davis wrote:
 Something like that could probably only be done if every range in the
 potentially large chain of wrapped ranges provided a means of getting at
 what type the previous one in the chain was, and very few ranges - if any
 - do that.

 However, I'm not quite sure what toCollection would buy you. Why does it
 really matter what type of container the range comes from originally given
 that you have to create a new container to put the elements of the range
 into such a container? And if you're putting the elements of a range in a
 new container, you can pick whatever container type you'd like, and since
 it has no real connection to the original container, I don't see why it
 would matter whether it was the same type of container. All you really
 need is the equivalent of std.array.array for whatever container you want
 to construct, and the container's constructor should provide that.

It's just like with the whole range idea, providing a common interface for iterating over a collection (and some other stuff). Here the idea is to have a common interface to transform the range back to a collection.

But what's special about the original container type? Once the range has been wrapped, it doesn't really have any connection to the container - particuarly when elements are likely to have been transformed and/or skipped or added such that they're no longer strongly linked with the original elements. As far as I can tell, the original container type becomes pretty much meaningless at that point.

I give up. Apparently you don't think it's useful. -- /Jacob Carlborg
May 04 2012
next sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-05-04 14:28, Chris Cain wrote:
 On Friday, 4 May 2012 at 11:46:34 UTC, Jacob Carlborg wrote:
 I give up. Apparently you don't think it's useful.

I'm not seeing it either, but it might help if you gave a concrete example of where it could/should be used and what benefits it might have. I think it'll be rather hard to come up with an example where the programmer wouldn't know what the original type was and have it actually matter.

What I actually want is to perform some operations on a collection and to have those return a collection. That's not how ranges work, I know, but I think it's more useful to get back a collection of than a range. -- /Jacob Carlborg
May 04 2012
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-05-04 19:15, Jonathan M Davis wrote:
 On Friday, May 04, 2012 13:46:33 Jacob Carlborg wrote:
 I give up. Apparently you don't think it's useful.

If you can come up with an example/reason why it would actually be useful, then great. But I don't see why it would ever matter what the original container type really was. You need the original range type in cases like std.container's remove function, but then the range must _be_ the original range type from that exact container in order to work, and there's no way that you could turn a wrapped range into the proper range for that, since you'd have to create a new container, and then the resultant range would be for the wrong container. And that's the only situation that I can think of where it really matters what the original container type was. If you want to construct a new container out of a range, then great, but since it's a new container, I don't see how it matters what the original container was unless you intend to assign the result to the new container or somesuch, in which case, you would already have access to the type, because you'd have a variable to assign to. - Jonathan M Davis

I have no problem if there's a new collection. I'm saying of the same _type_, not the same _collection_. As I've said in other posts in this thread, I mostly just want to assign the result of a range operation back to the original variable. Preferably I would like to not have to call any extra functions or constructors but that's not how ranges work. -- /Jacob Carlborg
May 04 2012
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, May 04, 2012 08:32:09 Jacob Carlborg wrote:
 On 2012-05-04 01:11, Stewart Gordon wrote:
 To sum it up, it can't be done in the general case. The range API
 doesn't know or care about the underlying data structure. That's half
 the point of it. The underlying data structure might not even exist. An
 example is a range used as a file stream, a random number generator or
 to lazily generate a mathematical sequence.

Yeah, I know, I know. It's all good in theory but I never found a use for it in practice and in most cases it's just annoying.
 Moreover, what would you want such a function to return if the range is:
 - a file stream with a cache
 - an array wrapper to loop infinitely through it?
 - a concatenation of ranges that may be of different types?

I was mostly thinking when the range originated from a collection. Where it's actually possible to transfer the range back to the original collection type.
 Moreover, even if there were some "range with an underlying container"
 classification, it would be an extra burden on the writer of the range
 wrapper to implement this.

No, I was thinking that the developer of the collection would provide that. I mean, it's already possible to transform a range to an array, I'm sure it's possible to transform it to a list of some kind as well. Then we could have this for example: collA.range.toArray(); collB.range.toList(); What I was asking for was if there is, or could be, a generic interface for this. Something like: collA.range.toCollection(); collA.range.toCollection(); If "collA" is an array "toCollection" would transform the range to an array, just as std.array.array does. If "collB" is a list the range would be transformed back in to a list.

Something like that could probably only be done if every range in the potentially large chain of wrapped ranges provided a means of getting at what type the previous one in the chain was, and very few ranges - if any - do that. However, I'm not quite sure what toCollection would buy you. Why does it really matter what type of container the range comes from originally given that you have to create a new container to put the elements of the range into such a container? And if you're putting the elements of a range in a new container, you can pick whatever container type you'd like, and since it has no real connection to the original container, I don't see why it would matter whether it was the same type of container. All you really need is the equivalent of std.array.array for whatever container you want to construct, and the container's constructor should provide that. - Jonathan M Davis
May 04 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, May 04, 2012 11:20:58 Jacob Carlborg wrote:
 On 2012-05-04 09:01, Jonathan M Davis wrote:
 Something like that could probably only be done if every range in the
 potentially large chain of wrapped ranges provided a means of getting at
 what type the previous one in the chain was, and very few ranges - if any
 - do that.
 
 However, I'm not quite sure what toCollection would buy you. Why does it
 really matter what type of container the range comes from originally given
 that you have to create a new container to put the elements of the range
 into such a container? And if you're putting the elements of a range in a
 new container, you can pick whatever container type you'd like, and since
 it has no real connection to the original container, I don't see why it
 would matter whether it was the same type of container. All you really
 need is the equivalent of std.array.array for whatever container you want
 to construct, and the container's constructor should provide that.

It's just like with the whole range idea, providing a common interface for iterating over a collection (and some other stuff). Here the idea is to have a common interface to transform the range back to a collection.

But what's special about the original container type? Once the range has been wrapped, it doesn't really have any connection to the container - particuarly when elements are likely to have been transformed and/or skipped or added such that they're no longer strongly linked with the original elements. As far as I can tell, the original container type becomes pretty much meaningless at that point. You should be able to put the elements that are in the range in whatever container type you want (which you can currently do very easily with arrays thanks to std.array.array and should be able to do with std.container's containers with their constructors), so you can put them in whatever container type is appropriate for whatever you're going to do with the elements. But I don't see how the _original_ container type matters for any of that. And when you consider that it's quite possible for a range to have no connection to a container whatsoever (e.g. anything in std.random), I just don't see how you could generically get at the type of the original container anyway (since there may not be one). Best case, you could create variable or alias which a range type _could_ have but doesn't necessarily have (similar to save or back) which could then hold the original container type (effectively creating yet another genre of range). But again, I don't see why that would actually be useful. - Jonathan M Davis
May 04 2012
prev sibling next sibling parent "Chris Cain" <clcain uncg.edu> writes:
On Friday, 4 May 2012 at 11:46:34 UTC, Jacob Carlborg wrote:
 I give up. Apparently you don't think it's useful.

I'm not seeing it either, but it might help if you gave a concrete example of where it could/should be used and what benefits it might have. I think it'll be rather hard to come up with an example where the programmer wouldn't know what the original type was and have it actually matter.
May 04 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 03 May 2012 04:41:50 -0400, Jacob Carlborg <doob me.com> wrote:

 On 2012-05-02 23:40, Jonathan M Davis wrote:
 On Wednesday, May 02, 2012 23:01:21 Jacob Carlborg wrote:
 Is there a general function for transforming a range back to the
 original type? If not, would it be possible to create one?

You mean that if you have something like auto range = getRangeFromSomewhere(); auto newRange = find(filter!func(range), value); you want to transform newRange back to the same type as range?

No, I want to transform newRange back to a collection, the same type as the original collection. I was thinking something like this: Collection c = new Collection(); c = c.filter!(x => x < 3).toCollection();

Why can't the last line be: c = new Collection(c.filter!(x => x < 3)); or more generically: c = new typeof(c)(c.filter!(x => x < 3)); ? -Steve
May 04 2012
prev sibling next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Friday, 4 May 2012 at 12:49:35 UTC, Steven Schveighoffer wrote:
 or more generically:

 c = new typeof(c)(c.filter!(x => x < 3));

 ?

That doesn't do the right thing when 'c' isn't a class type, so it's not really that generic. Struct types (the type of `new typeof(c)` is not `typeof(c)`!) and array types simply fail with your suggestion. I personally haven't decided whether I think a generic convention is useful here, but that code doesn't fit the bill.
May 04 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 04 May 2012 09:06:31 -0400, Jakob Ovrum <jakobovrum gmail.com>  
wrote:

 On Friday, 4 May 2012 at 12:49:35 UTC, Steven Schveighoffer wrote:
 or more generically:

 c = new typeof(c)(c.filter!(x => x < 3));

 ?

That doesn't do the right thing when 'c' isn't a class type, so it's not really that generic. Struct types (the type of `new typeof(c)` is not `typeof(c)`!) and array types simply fail with your suggestion.

Structs don't make very good containers. A slice is not really a container. But in any case, someone can make a function that's generic with a couple static ifs.
 I personally haven't decided whether I think a generic convention is  
 useful here, but that code doesn't fit the bill.

What exactly are you looking for? I mean, you want the original type back, so you can reassign, is that all? Something like this should work for that: c = makeContainer!typeof(c)(c.filter!(x => x < 3)); Implementation left as an exercise. -Steve
May 04 2012
prev sibling next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Friday, 4 May 2012 at 13:22:47 UTC, Steven Schveighoffer wrote:
 Structs don't make very good containers.  A slice is not really 
 a container.

Most containers in std.container are structs. A struct can do everything a class can do, for example, you can choose whether to use reference semantics or not. So I don't think the assertion that structs aren't good for containers is true, when they can do so much more than classes. There is still debate whether std.container's containers should be classes or structs, but even so, third-party containers might have different requirements.
 What exactly are you looking for?  I mean, you want the 
 original type back, so you can reassign, is that all?  
 Something like this should work for that:

 c = makeContainer!typeof(c)(c.filter!(x => x < 3));

 Implementation left as an exercise.

 -Steve

It would obviously be a dead simple function, the question is whether it's generally useful enough for the standard library, which I personally don't see it being, at least not until I see at least one good example. I was just pointing out the fact that it would require a function to abstract away the construction for all reasonable containers T. You would also have to decide on an explicit convention of construction when T is a user-defined type (e.g. define a constructor taking an input range), as such a function would effectively formalise it. (By the way, the template instantiation shortcut syntax only works when the only argument has exactly one token; your example code has an error.)
May 04 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 04 May 2012 11:21:06 -0400, Jakob Ovrum <jakobovrum gmail.com>  
wrote:

 On Friday, 4 May 2012 at 13:22:47 UTC, Steven Schveighoffer wrote:
 Structs don't make very good containers.  A slice is not really a  
 container.

Most containers in std.container are structs. A struct can do everything a class can do, for example, you can choose whether to use reference semantics or not. So I don't think the assertion that structs aren't good for containers is true, when they can do so much more than classes. There is still debate whether std.container's containers should be classes or structs, but even so, third-party containers might have different requirements.

Non-reference semantics for containers are very bad. Look at std::vector and how much inefficient code exists that passes it by value. A container has one important property with regard to its elements, it *owns* the elements. This screams reference semantics, because if you use value semantics, you need to *copy all the elements*. Yes, a struct can do reference semantics, but it makes little sense to fight the type system and shoehorn it into reference semantics, when classes are reference types by default.
 It would obviously be a dead simple function, the question is whether  
 it's generally useful enough for the standard library, which I  
 personally don't see it being, at least not until I see at least one  
 good example.

I think the use case is, instead of defining some transformation function X as a member of a container, you: 1. define X as a function that accepts a range and returns a range 2. define a way to obtain a range of all elements from a container 3. define a way to construct a new container from a range. Then you only have to define X once, instead of on every container type. And you can specialize some containers for X because of UFCS. See Jacob's example.
 You would also have to decide on an explicit convention of construction  
 when T is a user-defined type (e.g. define a constructor taking an input  
 range), as such a function would effectively formalise it.

Most definitely. I think any D-based container that can't be constructed from a range of values isn't worth implementing.
 (By the way, the template instantiation shortcut syntax only works when  
 the only argument has exactly one token; your example code has an error.)

Yes, I realized this after posting, but figured the point would get across ;) I sometimes miss being able to do this in my real code, the omission of parentheses for template instantiation is an awesome feature! -Steve
May 04 2012
prev sibling next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Friday, 4 May 2012 at 15:47:31 UTC, Steven Schveighoffer wrote:
 Yes, a struct can do reference semantics, but it makes little 
 sense to fight the type system and shoehorn it into reference 
 semantics, when classes are reference types by default.

It makes sense when you want something like reference counting.
 I think the use case is, instead of defining some 
 transformation function X as a member of a container, you:

 1. define X as a function that accepts a range and returns a 
 range
 2. define a way to obtain a range of all elements from a 
 container
 3. define a way to construct a new container from a range.

 Then you only have to define X once, instead of on every 
 container type.  And you can specialize some containers for X 
 because of UFCS.  See Jacob's example.

After a quick look over the thread again, I still don't see any real examples of use cases from Jacob (I admit I could still be missing it... somewhere...). Here's one scenario I came up with just now, anyway: T transmogrify(T)(T input) if(isInputRange!T) { auto transformed = map!foo(input); return makeContainer!T(transformed); } So basically, a templated function which, for some reason, wants to return the same type it receives. I still can't think of a real example similar to the above toy example, though. If the input just has to be an input range, isn't the output fine as an input range too? Isn't it better to leave the decision to the caller (whichever function on the way up the stack has the concrete types) of whether to do the expensive reconstruction operation? The code smells, is all I can say. So, I think the question is still whether such a function is appropriate for the standard library.
 Most definitely.  I think any D-based container that can't be 
 constructed from a range of values isn't worth implementing.

I agree, and I think the most natural way to implement this abstract interface would be using the constructor, but Jacob mentioned functions like toList() etc. earlier in the thread. Using the constructor is more idiomatic if Phobos is any example, but I suppose there could be reasons for not using it. (Obviously, array() only exists because there is no choice, slices being in-built).
 Yes, I realized this after posting, but figured the point would 
 get across ;)  I sometimes miss being able to do this in my 
 real code, the omission of parentheses for template 
 instantiation is an awesome feature!

It's always sad to see code failing to leverage it; often pops up with string tokens. It does make templates heaps less intimidating, and I applaud Andrei (sorry if this attribution is wrong!) for it :)
May 04 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, May 04, 2012 11:47:31 Steven Schveighoffer wrote:
 Yes, a struct can do reference semantics, but it makes little sense to
 fight the type system and shoehorn it into reference semantics, when
 classes are reference types by default.

A struct makes a lot more sense than a class when you need deterministic destruction. IIRC, the last time that it was discussed, it was decided that we'd go with structs rather than classes, because it would work better with custom allocators, but it was a rather involved discussion, and I don't remember all of the details. With a class though, you would _have_ to wrap it in a struct to be able to properly destroy it if it weren't garbage collected, or you'd have to manually free it, which would be far less safe and would make how you use the class vary widely based on the custom allocator. For instance, if your custom allocator used malloc and free, you'd need the container to be reference counted in order to clean itself up properly. The closest that you could get with classes without wrapping them in a struct would be to have the container allocated on the GC heap and have its guts allocated by the custom allocator. But if you used a struct, then the struct itself would be on the stack, avoiding the heap allocation and giving you the deterministic destruction that most allocators will need. If you're just going to use the GC heap, then classes are going to generally be better for reference types, because they naturally have reference semantics, but if custom allocators are involved, as far as I can tell, you pretty much need structs to get deterministic destruction and thus have the allocators work properly. - Jonathan M Davis
May 04 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, May 04, 2012 13:46:33 Jacob Carlborg wrote:
 I give up. Apparently you don't think it's useful.

If you can come up with an example/reason why it would actually be useful, then great. But I don't see why it would ever matter what the original container type really was. You need the original range type in cases like std.container's remove function, but then the range must _be_ the original range type from that exact container in order to work, and there's no way that you could turn a wrapped range into the proper range for that, since you'd have to create a new container, and then the resultant range would be for the wrong container. And that's the only situation that I can think of where it really matters what the original container type was. If you want to construct a new container out of a range, then great, but since it's a new container, I don't see how it matters what the original container was unless you intend to assign the result to the new container or somesuch, in which case, you would already have access to the type, because you'd have a variable to assign to. - Jonathan M Davis
May 04 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 04 May 2012 13:09:06 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Friday, May 04, 2012 11:47:31 Steven Schveighoffer wrote:
 Yes, a struct can do reference semantics, but it makes little sense to
 fight the type system and shoehorn it into reference semantics, when
 classes are reference types by default.

A struct makes a lot more sense than a class when you need deterministic destruction. IIRC, the last time that it was discussed, it was decided that we'd go with structs rather than classes, because it would work better with custom allocators, but it was a rather involved discussion, and I don't remember all of the details.

Allocation and destruction are orthogonal to the problem. For example, in working on the new std.io, I've had to make RefCounted!(class) work, All I do is allocate the class data into the C heap. The issue is, do you want pass by reference, or pass by value. My opinion is that it should always be pass by reference for container types. And classes make that *so* much easier. With structs, you have to jump through hoops to get them to properly be reference types. -Steve
May 04 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, May 04, 2012 13:38:24 Steven Schveighoffer wrote:
 On Fri, 04 May 2012 13:09:06 -0400, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:
 On Friday, May 04, 2012 11:47:31 Steven Schveighoffer wrote:
 Yes, a struct can do reference semantics, but it makes little sense to
 fight the type system and shoehorn it into reference semantics, when
 classes are reference types by default.

A struct makes a lot more sense than a class when you need deterministic destruction. IIRC, the last time that it was discussed, it was decided that we'd go with structs rather than classes, because it would work better with custom allocators, but it was a rather involved discussion, and I don't remember all of the details.

Allocation and destruction are orthogonal to the problem. For example, in working on the new std.io, I've had to make RefCounted!(class) work, All I do is allocate the class data into the C heap.

It's not orthogonal if you want the allocation to be internal to the type and not have to worry about wrapping the container in a struct to actually get it to deallocate properly. For instance, you can allocate a class with malloc, but without a wrapper, you're going to have to keep track of the fact that it was allocated with malloc and make sure that you destroy it and free it. But if the container is a struct, then all of that can be internal, because the struct itself is on the stack rather than the heap. I don't see how you could use a custom allocator with a class and not have a wrapper, which means that using a custom allocator would affect the API of anything using containers that used them. As I understand it, Andrei intends for the custom allocators to be dynamic, which means that the type of the container will be the same regardless of the allocator used. And if that's the case, I don't see how you can safely use classes as containers without always wrapping them in structs. And if you're going to do that, why whould you make them classes in the first place?
 The issue is, do you want pass by reference, or pass by value. My opinion
 is that it should always be pass by reference for container types. And
 classes make that *so* much easier.
 
 With structs, you have to jump through hoops to get them to properly be
 reference types.

Yes. std.container's container types will most definitely be reference types, and yes, in general, that means that using classes would be better, but custom allocators throw a major wrench in that, because you need to control where the class is (which doesn't work very well without a wrapper, since without one you have to worry about freeing it manually), and many custom allocators need deterministic destruction, which classes don't provide. I believe that this was the most recent discussion on the issue: http://forum.dlang.org/post/mailman.1543.1323832143.24802.digitalmars- d puremagic.com We'll have to see what Andrei actually proposes though, since he's been working on the custom allocators, and I don't know what has and hasn't changed as he's been working on them. - Jonathan M Davis
May 04 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 04 May 2012 13:59:02 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Friday, May 04, 2012 13:38:24 Steven Schveighoffer wrote:
 Allocation and destruction are orthogonal to the problem. For example,  
 in
 working on the new std.io, I've had to make RefCounted!(class) work, All
 I do is allocate the class data into the C heap.

It's not orthogonal if you want the allocation to be internal to the type and not have to worry about wrapping the container in a struct to actually get it to deallocate properly.

Allocation of the container itself is a different problem than allocation of its internals. I think you are confusing the two. For example, I can have a red black tree that allocates all its elements using malloc, then allocate the class itself on the stack using scoped so it becomes deallocated after exiting the scope. Or I can use malloc for internal allocation, and use new to allocate on the heap, and let the GC clean up the tree (and the malloc-based allocator stored in the class cleans up its elements).
 For instance, you can allocate a class with malloc,
 but without a wrapper, you're going to have to keep track of the fact  
 that it
 was allocated with malloc and make sure that you destroy it and free it.

Yes, and this has nothing to do with the custom allocator needed to allocate its elements. The container owns the elements, it doesn't own itself. Even a struct can be allocated on the GC heap.
 As I understand it, Andrei intends for the custom allocators to be  
 dynamic,
 which means that the type of the container will be the same regardless  
 of the
 allocator used. And if that's the case, I don't see how you can safely  
 use
 classes as containers without always wrapping them in structs. And if  
 you're
 going to do that, why whould you make them classes in the first place?

Again, these are orthogonal problems. Who allocates and owns the container is different than who allocates and owns the elements. The container is responsible for cleaning up the elements (via the allocator it is handed), someone else is responsible for cleaning up the container. It could potentially be the same allocator, but it also could potentially be something completely different. The only requirement is that the allocator *must* live at least as long as the type itself (if you are going to do dynamic allocators). This rules out a simple GC-allocated reference type as an allocator, but the container itself can be GC allocated. Dcollections does not currently use dynamic allocators, although it could be made to do so. Currently, the allocator is a struct which is stored inside the container. -Steve
May 04 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 04 May 2012 12:32:39 -0400, Jakob Ovrum <jakobovrum gmail.com>  
wrote:

 On Friday, 4 May 2012 at 15:47:31 UTC, Steven Schveighoffer wrote:
 I think the use case is, instead of defining some transformation  
 function X as a member of a container, you:

 1. define X as a function that accepts a range and returns a range
 2. define a way to obtain a range of all elements from a container
 3. define a way to construct a new container from a range.

 Then you only have to define X once, instead of on every container  
 type.  And you can specialize some containers for X because of UFCS.   
 See Jacob's example.

After a quick look over the thread again, I still don't see any real examples of use cases from Jacob (I admit I could still be missing it... somewhere...).

This one: Collection c = new Collection(); c = c.filter!(x => x < 3).toCollection(); filter isn't a property of c, it's a range-producing function. So I only have to define filter once, as a range accepting, range producing function. And any container type, as long as it can produce a range, can use this as a pseudo method (via UFCS) to make a filtered copy of itself. -Steve
May 04 2012
prev sibling next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Friday, 4 May 2012 at 19:17:13 UTC, Steven Schveighoffer wrote:
 This one:

 Collection c = new Collection();
 c = c.filter!(x => x < 3).toCollection();

 filter isn't a property of c, it's a range-producing function.  
 So I only have to define filter once, as a range accepting, 
 range producing function.  And any container type, as long as 
 it can produce a range, can use this as a pseudo method (via 
 UFCS) to make a filtered copy of itself.

 -Steve

That's not a real example, that's pretty much the same example I provided below the part you quoted.
May 04 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 04 May 2012 16:05:25 -0400, Jakob Ovrum <jakobovrum gmail.com>  
wrote:

 On Friday, 4 May 2012 at 19:17:13 UTC, Steven Schveighoffer wrote:
 This one:

 Collection c = new Collection();
 c = c.filter!(x => x < 3).toCollection();

 filter isn't a property of c, it's a range-producing function.  So I  
 only have to define filter once, as a range accepting, range producing  
 function.  And any container type, as long as it can produce a range,  
 can use this as a pseudo method (via UFCS) to make a filtered copy of  
 itself.

 -Steve

That's not a real example, that's pretty much the same example I provided below the part you quoted.

First, what would you consider a real example? Second, there's an important piece of the use case that your sample lacks -- Jacob is rebinding the result back to the original item. So for example, I could see code like this: void displayResults(Container c) { if(maxvalue) c = c.filter!(x => x < maxvalue).makeContainer!Container(); // proceed to display elements from c } -Steve
May 04 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, May 04, 2012 16:37:23 Steven Schveighoffer wrote:
 On Fri, 04 May 2012 16:05:25 -0400, Jakob Ovrum <jakobovrum gmail.com>
 
 wrote:
 On Friday, 4 May 2012 at 19:17:13 UTC, Steven Schveighoffer wrote:
 This one:
 
 Collection c = new Collection();
 c = c.filter!(x => x < 3).toCollection();
 
 filter isn't a property of c, it's a range-producing function. So I
 only have to define filter once, as a range accepting, range producing
 function. And any container type, as long as it can produce a range,
 can use this as a pseudo method (via UFCS) to make a filtered copy of
 itself.
 
 -Steve

That's not a real example, that's pretty much the same example I provided below the part you quoted.

First, what would you consider a real example? Second, there's an important piece of the use case that your sample lacks -- Jacob is rebinding the result back to the original item. So for example, I could see code like this: void displayResults(Container c) { if(maxvalue) c = c.filter!(x => x < maxvalue).makeContainer!Container(); // proceed to display elements from c }

std.container has make, which should do essentially that. And since you have the original container, you know what its type is, so there's no need to query the range for the original container type. Something like this should work: c = make!Container(filter!(x => x < maxvalue)(c)); If it doesn't, then make and/or the container needs to be improved so that it does. - Jonathan M Davis
May 04 2012
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, May 04, 2012 21:24:05 Jacob Carlborg wrote:
 I have no problem if there's a new collection. I'm saying of the same
 _type_, not the same _collection_. As I've said in other posts in this
 thread, I mostly just want to assign the result of a range operation
 back to the original variable.

Well, if you have a variable to assign to, then you know the type already. You don't need to query the range. You just need a way to create an instance of that container from the range. If it's an array, then use std.array.array. If it's a string, you can use std.conv.to (so that you get a string rather than a dstring). If it's standard a container, then std.container.make should do the trick. If it's another type, then as long as the type's constructor takes a range, you can just use the constructor. In general, it should just be one function call.
 Preferably I would like to not have to
 call any extra functions or constructors but that's not how ranges work.

A filter function which returned the same container type as it was passed would be doing something pretty similar to creating a range with the elements that match the predicate and creating a container from that. It might be more efficient depending on exactly how it was done and what the compiler's able to optimize, but it would be far less flexible. Ranges serve as building blocks, allowing us to chain functions in way that would be _really_ ineffecient with containers (using just one function might end up being more efficient, but if every such function in a chain is creating a new container, it would get very inefficient very quickly). Ranges end up being far more powerful. Yes, you then have to worry about putting the range in a container if you really want a container, but it should only take one function call, so I would think that the flexibility that ranges buy you would be well worth that small annoyance. - Jonathan M Davis
May 04 2012