Re: Swap front for char[] input ranges
On Monday, 19 December 2016 at 20:26:26 UTC, Ali Çehreli wrote: On 12/19/2016 06:09 AM, RazvanN wrote: > [...] wrote: >> [...] InputRanges. >> [...] following > [...] char[] > [...] function, so > [...] http://dlang.org/phobos/std_algorithm_mutation.html#bringToFront [...] No need to mention it. It is an honor to be able contribute to this great language. [...] That is right, I am working on that particular bug. After talking with AndreiA, I submitted this PR [1]. It treats the case of char[], but I am not really sure how the constraints should be applied to the function since it seems there are a lot of combinations (especially if char[] is supported). [1] https://github.com/dlang/phobos/pull/4970
Re: Swap front for char[] input ranges
On 12/19/2016 06:09 AM, RazvanN wrote:
> On Monday, 19 December 2016 at 12:25:02 UTC, Ali Çehreli wrote:
>> On 12/19/2016 02:41 AM, RazvanN wrote:
>> > [...]
>>
>> As your comments make it clear below, they cannot be InputRanges.
>>
>> > [...]
>> swapping code
>> > [...]
>>
>> Obivously, tmp1 and tmp2 are unusued there. :)
>>
>> > [...]
>> passed.
>> > [...]
>> state
>> > [...]
>> is:
>> > [...]
>> input ranges
>> > [...]
>>
>> Not possible... It's ok to use something similar to the following
>> template constraint:
>>
>> void foo(R1, R2)(R1 r1, R2 r2)
>> if ((hasSwappableElements!R1 && hasSwappableElements!R2) ||
>> (hasLvalueElements!R1 && hasLvalueElements!R2)) {
>> // ...
>> }
>>
>> Ali
>
> In this case, the bringToFront function [1] should not accept char[]
> as parameters? Or a special path should be added in the function, so
> that char[] are treated specially?
>
> [1] http://dlang.org/phobos/std_algorithm_mutation.html#bringToFront
First, thanks to you and to your colleagues very much for improving D
with these fixes. :)
I think you're working on the following bug:
https://issues.dlang.org/show_bug.cgi?id=16959
Regarding the compilation error inside swapFront, its template
constraints should be fixed as I suggested earlier. It cannot work with
any two InputRanges. I think it warrants its separate bug.
private void swapFront(R1, R2)(R1 r1, R2 r2)
if (isInputRange!R1 && isInputRange!R2)
{
static if (is(typeof(swap(r1.front, r2.front
{
swap(r1.front, r2.front);
}
else
{
auto t1 = moveFront(r1), t2 = moveFront(r2);
r1.front = move(t2);
r2.front = move(t1);
}
}
Regarding bringToFront:
1) Reading its documentation, bringToFront() seems to be an algorithms
that mutates its ranges (not just give a brought-to-front view of
existing data). If so, its argument cannot simply be an InputRange
because there are InputRanges out there where you cannot write it their
.front. (char[] is just one example.):
size_t bringToFront(Range1, Range2)(Range1 front, Range2 back)
if (isInputRange!Range1 && isForwardRange!Range2)
{
// ...
}
Its template constraint must also be changed to include a combination of
hasLvalueElements() and hasMobileElements().
2) After fixing that, a char[] can indeed bring characters to front but
it would be an expensive operation where a multi-byte Unicode character
would necessarily move a single-byte Unicode character to the right.
(Additionally, depending on its length, the first argument may allow
only a partial UTF-8 encoding at its end. Fail! :) )
I don't know how to allow or encode such an expensive operation which is
outside the documented "Ο(max(front.length, back.length))" complexity of
bringToFront(). If it were me, I would look for possibilities to change
the behavior and make bringToFront() a non-mutating algorithm.
What do others think?
Ali
Re: Swap front for char[] input ranges
On Monday, 19 December 2016 at 12:25:02 UTC, Ali Çehreli wrote:
On 12/19/2016 02:41 AM, RazvanN wrote:
> [...]
As your comments make it clear below, they cannot be
InputRanges.
> [...]
swapping code
> [...]
Obivously, tmp1 and tmp2 are unusued there. :)
> [...]
passed.
> [...]
state
> [...]
is:
> [...]
input ranges
> [...]
Not possible... It's ok to use something similar to the
following template constraint:
void foo(R1, R2)(R1 r1, R2 r2)
if ((hasSwappableElements!R1 && hasSwappableElements!R2) ||
(hasLvalueElements!R1 && hasLvalueElements!R2)) {
// ...
}
Ali
In this case, the bringToFront function [1] should not accept
char[]
as parameters? Or a special path should be added in the function,
so that char[] are treated specially?
[1]
http://dlang.org/phobos/std_algorithm_mutation.html#bringToFront
Re: Swap front for char[] input ranges
On Monday, 19 December 2016 at 10:41:46 UTC, RazvanN wrote:
Hi,
I have a function which accepts 2 input Ranges and swaps the
first element in Range1 with the first element in Range2. The
swapping code looks something like this :
static if (is(typeof(swap(r1.front, r2.front
{
swap(r1.front, r2.front);
}
else
{
auto t1 = moveFront(r1), t2 = moveFront(r2);
auto tmp1 = r1.front;
auto tmp2 = r2.front;
r1.front = move(t2);
r2.front = move(t1);
}
This code works for most cases, except when 2 char[] are passed.
In that case, the compilation fails with error messages which
state
that r1.front and r2.front are not Lvalues. So, my question is:
how can I swap the 2 elements since in the case of char[] input
ranges
the front property does not return a reference?
does it work if you cast the 2 char[] as 2 ubyte[] ?
If so, it's a problem with narrow strings and utf8 decoding...i.e
there's no guarantee that each code unit in r1 matches to a code
unit in r2.
Swap front for char[] input ranges
Hi,
I have a function which accepts 2 input Ranges and swaps the
first element in Range1 with the first element in Range2. The
swapping code looks something like this :
static if (is(typeof(swap(r1.front, r2.front
{
swap(r1.front, r2.front);
}
else
{
auto t1 = moveFront(r1), t2 = moveFront(r2);
auto tmp1 = r1.front;
auto tmp2 = r2.front;
r1.front = move(t2);
r2.front = move(t1);
}
This code works for most cases, except when 2 char[] are passed.
In that case, the compilation fails with error messages which
state
that r1.front and r2.front are not Lvalues. So, my question is:
how can I swap the 2 elements since in the case of char[] input
ranges
the front property does not return a reference?
Re: I wrote a function that accepts input ranges, and I get compile errors when passing an array
On Saturday, 28 May 2016 at 20:43:00 UTC, pineapple wrote: On Saturday, 28 May 2016 at 16:25:02 UTC, Seb wrote: If you are interested how it works under the hood - it's pretty simple & elegant: I checked up on the phobos implementation and found that arrays are mutated when iterated over as ranges, which didn't rest well with me. Nor did the idea of importing some module having such a significant side-effect as whether some type can act as a range or not. So I ended up making a sort of factory that turns arbitrary objects into ranges, including arrays. Seems to work pretty well. Arrays in D work differently to other languages. That's why we call them Slices ;-) See: https://dlang.org/d-array-article.html Phobos just modifies the pointer - so `a = a[1 .. $];` is nothing more than creating a new pointer. are mutated when iterated over as ranges, Btw all ranges are modified during iteration, they have a state and with every popFront you change that. If you want to save the state before, you can call `.save` if it's at least a ForwardRange
Re: I wrote a function that accepts input ranges, and I get compile errors when passing an array
On Saturday, 28 May 2016 at 16:25:02 UTC, Seb wrote: If you are interested how it works under the hood - it's pretty simple & elegant: I checked up on the phobos implementation and found that arrays are mutated when iterated over as ranges, which didn't rest well with me. Nor did the idea of importing some module having such a significant side-effect as whether some type can act as a range or not. So I ended up making a sort of factory that turns arbitrary objects into ranges, including arrays. Seems to work pretty well.
Re: I wrote a function that accepts input ranges, and I get compile errors when passing an array
On Friday, 27 May 2016 at 14:59:25 UTC, Adam D. Ruppe wrote: On Friday, 27 May 2016 at 14:54:30 UTC, pineapple wrote: I've encountered one remarkable difference: The phobos function accepts arrays and mine does not. add `import std.array;` i think to your module and it should make arrays ranges you would get a more fine-grained import with std.range (or more even more detailed std.range.primitives). If you are interested how it works under the hood - it's pretty simple & elegant: https://github.com/dlang/phobos/blob/master/std/range/primitives.d#L2038
Re: I wrote a function that accepts input ranges, and I get compile errors when passing an array
On Friday, 27 May 2016 at 14:54:30 UTC, pineapple wrote: I've encountered one remarkable difference: The phobos function accepts arrays and mine does not. add `import std.array;` i think to your module and it should make arrays ranges
I wrote a function that accepts input ranges, and I get compile errors when passing an array
I'm writing my own map function modeled after the one in phobos.
(because I feel like it, that's why. good learning experience.)
I've encountered one remarkable difference: The phobos function
accepts arrays and mine does not. I understand why - I'm calling
methods that arrays don't have - but what I don't understand is
why the phobos function _does_ work. I haven't been able to find
what in the phobos code accounts for iterables that aren't ranges.
What am I missing?
enum canMap(T) = isInputRange!(Unqual!T);
auto map(alias func, Range)(Range range) if(canMap!Range){
return Mapping!(func, Range)(range);
}
struct Mapping(alias func, Range) if(canMap!Range){
alias URange = Unqual!Range;
Range input;
this(URange input){
this.input = input;
}
void popFront(){
this.input.popFront();
}
@property auto ref front(){
return func(this.input.front);
}
static if(isBidirectionalRange!URange){
@property auto ref back(){
return func(this.input.back);
}
void popBack(){
this.input.popBack();
}
}
static if(isInfinite!URange){
enum bool empty = false;
}else{
@property bool empty(){
return this.input.empty;
}
}
static if(isRandomAccessRange!URange){
static if(is(typeof(URange.opIndex) == function)){
alias Index = Parameters!(URange.opIndex)[0];
}else{
alias Index = size_t;
}
auto ref opIndex(Index index){
return func(this.input[index]);
}
}
static if(is(typeof(URange.opDollar))){
alias opDollar = URange.opDollar;
}
static if(hasLength!URange){
@property auto length(){
return this.input.length;
}
}
static if(hasSlicing!URange){
static if(is(typeof(URange.opIndex) == function)){
alias SliceIndex = Parameters!(URange.opIndex)[0];
}else{
alias SliceIndex = size_t;
}
auto opSlice(SliceIndex low, SliceIndex high){
return typeof(this)(this.input[low .. high]);
}
}
static if(isForwardRange!URange){
@property auto save(){
return typeof(this)(this.input.save);
}
}
}
version(unittest) import mach.error.unit;
unittest{
import std.stdio;
//import std.algorithm : map; // Works with this
// no property 'popFront', etc for type 'int[]'
writeln(
[1, 2, 3].map!((item) => (item * item))
);
}
Tangentially related question - Why does phobos use
isInputRange!(Unqual!T) instead of just isInputRange!T? What's
the functional difference here?
Re: Input ranges
On Sunday, 19 April 2015 at 23:49:08 UTC, anonymous wrote: On Sunday, 19 April 2015 at 21:42:23 UTC, Ulrich Küttler wrote: groupBy is a nice example as it laboriously adds reference semantics to forward ranges but assumes input ranges to posses reference semantics by themselves. All ranges are input ranges, though. Input ranges are the least specialised category. I think it's a mistake to assume/require anything only for input ranges that are not forward ranges. Yes and no. It is reasonable to provide special implementations for ranges that are just input ranges. This is what groupBy does. The user gets a function that works with all kinds of ranges. I guess we could require reference semantics for all input ranges (including forward ranges and higher-ups). That would be a rather clean way out of this mess. But it would be a major effort. And I guess it would hurt performance, maybe a lot. Definitely, general reference semantics would solve a ton of difficulty. However, this would not be D anymore. This seems to be the catch: For optimal performance memory layout is important. You cannot hide it behind an interface. At this point the solution in byLineCopy feels ad hoc. I think byLineCopy solves a different problem. ByLine already has this: https://github.com/D-Programming-Language/phobos/blob/v2.067.0/std/stdio.d#L1592-L1598 The same indirection in byLineCopy. This is what I was referring to: https://github.com/D-Programming-Language/phobos/blob/v2.067.0/std/stdio.d#L1783-L1789 Whoever did that knew very well what is going on.
Re: Input ranges
On Saturday, 18 April 2015 at 22:01:56 UTC, Ulrich Küttler wrote: Input ranges from std.stdio are used for reading files. So assuming we create a file auto f = File(test.txt, w); f.writeln(iota(5).map!(a = repeat(to!string(a), 4)).joiner.joiner(\n)); f.close(); We should be able groupBy (chunkBy) its lines: writeln(File(test.txt).byLine.groupBy!((a,b) = a == b)); The result is just one group, that is all lines are considered equal: [[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]] Alas, byLine reuses the same buffer for each line and thus groupBy keeps comparing each line with itself. There is a version of byLine that makes copies: writeln(File(test.txt).byLineCopy.groupBy!((a,b) = a == b)); Indeed, the result is as expected: [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]] Yeah, byLine is dangerous. byLineCopy should probably have been the default. Maybe we should rename byLine to byLineNoCopy (doing the proper deprecation dance, of course). A final test with the undocumented byRecord method (the mapping after groupBy is for beauty only and does not change the result): writeln(File(test.txt) .byRecord!string(%s) .groupBy!((a,b) = a == b) .map!(map!(a = a[0]))); Here, the result is most peculiar: [[0, 0, 0, 0], [1, 1, 1], [2, 2, 2], [3, 3, 3], [4, 4, 4]] Is byRecord broken? (It is undocumented after all.) In a way, because it does not contain any indirection. The current fields tuple is a simple member of the ByRecord struct. In contrast, the ByLineCopy struct is just a wrapper to a ref counted ByLineCopyImpl struct with a simple note: /* Ref-counting stops the source range's ByLineCopyImpl * from getting out of sync after the range is copied, e.g. * when accessing range.front, then using std.range.take, * then accessing range.front again. */ I am uncomfortable at this point. Simple and efficient input ranges fail in unexpected ways. Internal indirections make all the difference. It feels like input ranges are hiding something that should not be hidden. What am I missing? I guess the problem is the mix of value and reference semantics. ByRecord's `current` is a value, but its `file` has reference semantics. So, a copy of a ByRecord affects one part of the original but not the other. Maybe copying should be `@disable`d for such ranges/structs. Then you couldn't pass it by value to groupBy. Instead you would have to use something like (the fixed version of) refRange, which works properly.
Re: Input ranges
On Sunday, 19 April 2015 at 21:42:23 UTC, Ulrich Küttler wrote: groupBy is a nice example as it laboriously adds reference semantics to forward ranges but assumes input ranges to posses reference semantics by themselves. All ranges are input ranges, though. Input ranges are the least specialised category. I think it's a mistake to assume/require anything only for input ranges that are not forward ranges. I guess we could require reference semantics for all input ranges (including forward ranges and higher-ups). That would be a rather clean way out of this mess. But it would be a major effort. And I guess it would hurt performance, maybe a lot. [...] Again, I agree. Disallow copying for such ranges would prevent the error, still it would be a bit harsh. It is not just groupBy that goes astray. You can also get strange results from take: auto r = File(test.txt).byRecord!string(%s); foreach (i; 0 .. 5) writeln(r.take(4).map!(a = a[0])); That would also not be possible if ByRecord had an `@disable this(this);`. But I'm not at all sure that this is the way to go. It's bound to be forgotten, and there are probably places where it's needlessly restrictive. I was hoping to find some communication how input ranges should be done. I'm right there with you. This is all a bit iffy. I suspect that this is an oversight in the design of ranges, as the documentation of std.range doesn't say anything on the topic. This may be too advanced for D.learn. I don't think Andrei and Walter come down here very often. Maybe take it to the general board. At this point the solution in byLineCopy feels ad hoc. I think byLineCopy solves a different problem. ByLine already has this: https://github.com/D-Programming-Language/phobos/blob/v2.067.0/std/stdio.d#L1592-L1598
Re: Input ranges
On Sunday, 19 April 2015 at 11:33:26 UTC, anonymous wrote: I guess the problem is the mix of value and reference semantics. ByRecord's `current` is a value, but its `file` has reference semantics. So, a copy of a ByRecord affects one part of the original but not the other. I agree. Yet I am convinced most (all?) proper input ranges read input from an external source. (Reference semantic right there.) Input ranges are one-pass ranges after all. Therefore, reference semantics are required in any case (unless the use of the range is known beforehand.) groupBy is a nice example as it laboriously adds reference semantics to forward ranges but assumes input ranges to posses reference semantics by themselves. Maybe copying should be `@disable`d for such ranges/structs. Then you couldn't pass it by value to groupBy. Instead you would have to use something like (the fixed version of) refRange, which works properly. Again, I agree. Disallow copying for such ranges would prevent the error, still it would be a bit harsh. It is not just groupBy that goes astray. You can also get strange results from take: auto r = File(test.txt).byRecord!string(%s); foreach (i; 0 .. 5) writeln(r.take(4).map!(a = a[0])); I was hoping to find some communication how input ranges should be done. At this point the solution in byLineCopy feels ad hoc.
Input ranges
It seems input ranges without any indirection in memory are not working well with algorithms. This seems to be understood by the D community. I did not know. Here is my story on the topic so far: Recently, I learned that I did not know input ranges much at all, totally misjudging std.range.refRange in its usefulness to input ranges: https://github.com/D-Programming-Language/phobos/pull/3123 At this point some experiments might be in order. (using 2.067.0) Input ranges from std.stdio are used for reading files. So assuming we create a file auto f = File(test.txt, w); f.writeln(iota(5).map!(a = repeat(to!string(a), 4)).joiner.joiner(\n)); f.close(); We should be able groupBy (chunkBy) its lines: writeln(File(test.txt).byLine.groupBy!((a,b) = a == b)); The result is just one group, that is all lines are considered equal: [[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]] Alas, byLine reuses the same buffer for each line and thus groupBy keeps comparing each line with itself. There is a version of byLine that makes copies: writeln(File(test.txt).byLineCopy.groupBy!((a,b) = a == b)); Indeed, the result is as expected: [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]] A final test with the undocumented byRecord method (the mapping after groupBy is for beauty only and does not change the result): writeln(File(test.txt) .byRecord!string(%s) .groupBy!((a,b) = a == b) .map!(map!(a = a[0]))); Here, the result is most peculiar: [[0, 0, 0, 0], [1, 1, 1], [2, 2, 2], [3, 3, 3], [4, 4, 4]] Is byRecord broken? (It is undocumented after all.) In a way, because it does not contain any indirection. The current fields tuple is a simple member of the ByRecord struct. In contrast, the ByLineCopy struct is just a wrapper to a ref counted ByLineCopyImpl struct with a simple note: /* Ref-counting stops the source range's ByLineCopyImpl * from getting out of sync after the range is copied, e.g. * when accessing range.front, then using std.range.take, * then accessing range.front again. */ I am uncomfortable at this point. Simple and efficient input ranges fail in unexpected ways. Internal indirections make all the difference. It feels like input ranges are hiding something that should not be hidden. What am I missing?
Re: Using input ranges with std.regex?
On Wednesday, 25 April 2012 at 21:43:11 UTC, Dmitry Olshansky wrote: On 25.04.2012 23:08, H. S. Teoh wrote: Does std.regex support input ranges to match()? Or do I need to convert to string first? For now, yes you have to convert them. Any random access range of code units should do the trick but stringish template constraints might kill that. I plan to extend this eventually. The problematic point is that match internally is delimited by integer offsets (indices). Forward ranges technically can work (the match then will return something like take(..., n);) with a bunch of extra .save calls. Input ranges can't be used at all. Is there any progress on this thing?
Using input ranges with std.regex?
Does std.regex support input ranges to match()? Or do I need to convert to string first? Thanks! T -- Tell me and I forget. Teach me and I remember. Involve me and I understand. -- Benjamin Franklin
Re: Using input ranges with std.regex?
On 25.04.2012 23:08, H. S. Teoh wrote: Does std.regex support input ranges to match()? Or do I need to convert to string first? For now, yes you have to convert them. Any random access range of code units should do the trick but stringish template constraints might kill that. I plan to extend this eventually. The problematic point is that match internally is delimited by integer offsets (indices). Forward ranges technically can work (the match then will return something like take(..., n);) with a bunch of extra .save calls. Input ranges can't be used at all. -- Dmitry Olshansky
