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
parent reply "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
parent reply "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
parent reply "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
parent reply "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
parent reply "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
next sibling parent reply "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
next sibling parent reply "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
parent reply "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
next sibling parent reply "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
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 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 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 reply "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
parent reply "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
parent reply "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
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 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 reply 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
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 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
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 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
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 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
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 reply "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
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 reply "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
parent reply 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
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