www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.range.iota enhancement: supporting more types (AKA issue 10762)

reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
Sorry for the amount of text, but I tried to explain everything 
in a clear and simple way.
I'm willing to volunteer for adding support for more types in 
iota. The relevant discussion is: 
https://d.puremagic.com/issues/show_bug.cgi?id=10762

A few preliminary considerations:
- iota() currently returns a Random Access range, and I'm sure 
nobody would agree to downgrade the result to a ForwardRange or 
an InputRange, because that would break an unknown amount of code.
- I think everyone agrees that even after enhancements, iota() 
should always return a RA range, even if we use types that are 
currently not supported. It would make little sense returning 
different kind of ranges for different input types.

Let's define the types: When calling iota(start,end,inc)
   S=typeof(start),
   E=typeof(end),
   I=typeof(inc),
   C=CommonType!(S,E).

My proposal:
iota(start, end, inc) accepts any type, as long as
     {C c; c += inc; c < end;} or {C c; c = c + inc; c < end;} is 
valid code;
Since inc type might not be directly comparable to 0, we also 
check if (start + inc < start). If this returns true, this means 
that "inc is negative" in a more general sense. We can use this 
information to return an empty range when needed, respecting the 
behaviour defined by the library reference. eg: (start < end && 
inc < 0) => return empty range.
end is not required to be equal to (start + n*inc) for any given 
n; eg: iota(4, 9, 2) should be valid and return [4, 6, 8]. We can 
discuss if this makes sense or should be changed, but I think it 
would be better this way.
If the code {int n; I n_inc = n * inc;} is valid, this 
instruction is used for providing O(1) access for opIndex and 
opSlice methods.
If the code {C c; c -= inc;} or {C c; c = c - inc} is valid, this 
instruction is used for providing O(1) access for popBack() 
method.
If no optimization is available, the code will provide O(n) 
performance for those methods.
The real issue however is that construction of the range might 
end up taking O(n) time, because we have to provide the length 
and the back property. One work around is computing those lazily 
only if the user requests them.
By doing this, anyone only using iota() for forward iteration 
will still obtain O(1) performance.

iota(start, end) accepts any type, as long as
     {C c; ++c; c < end;} or {iota(start, end, 1);} is valid code. 
If both forms are valid, the iota(start, end, 1) version is 
preferred (allowing possible optimizations as discussed before).
Everything else ends up being the same as before: popBack() can 
be optimized if {--c;} is valid code, the opIndex, opSlice, back 
and length methods will take O(n) time, no way around this sadly.

hsteoh suggested:
     If start+inc is *not* supported but start-- is, and end < 
start, should we support iota(start,end)?
I think this idea should be discarded since some code could 
quickly become a minefield:
type T implements ++t and --t;
type P only implements ++p;
t1 < t2 => iota(t2, t1) has a way to compute a non-empty range;
p1 < p2 => iota(p2, p1) can do nothing but return an empty range;
And this behaviour really smells bad, IMHO. The only way to solve 
this is requiring opUnary!"--" being implemented for the type to 
be used, and I am not sure about this (most iota uses only really 
need ++).

Any suggestion/critique? If this looks good to you, I can start 
working on it. If you disagree on something (and I know you have 
something to say!), discussion is more than welcome!

Francesco
Dec 23 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Francesco Cattoglio:

 - iota() currently returns a Random Access range, and I'm sure 
 nobody would agree to downgrade the result to a ForwardRange or 
 an InputRange, because that would break an unknown amount of 
 code.
 ...
 Everything else ends up being the same as before: popBack() can 
 be optimized if {--c;} is valid code, the opIndex, opSlice, 
 back and length methods will take O(n) time, no way around this 
 sadly.
If the new iota accepts new types, then no existing code is using iota for such cases. So you are not breaking code is you offer a more restricted range for such types, avoiding O(n) behavior for them. Bye, bearophile
Dec 23 2013
parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Monday, 23 December 2013 at 15:23:45 UTC, bearophile wrote:
 If the new iota accepts new types, then no existing code is 
 using iota for such cases. So you are not breaking code is you 
 offer a more restricted range for such types, avoiding O(n) 
 behavior for them.
I do realize this, but I don't really like having iota() returning different ranges for different types. Do you think this would make sense? Something like "iota returns a RA range for arithmetical types and a ForwardRange for any other type supporting opUnary!++"?
Dec 23 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Francesco Cattoglio:

 Do you think this would make sense?
Other things in Phobos work like this. Usually in Phobos Big-O requirements are more important than keeping the range type unchanged. Bye, bearophile
Dec 23 2013
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Dec 23, 2013 at 03:30:12PM +0000, Francesco Cattoglio wrote:
 On Monday, 23 December 2013 at 15:23:45 UTC, bearophile wrote:
If the new iota accepts new types, then no existing code is using
iota for such cases. So you are not breaking code is you offer a
more restricted range for such types, avoiding O(n) behavior for
them.
I do realize this, but I don't really like having iota() returning different ranges for different types. Do you think this would make sense? Something like "iota returns a RA range for arithmetical types and a ForwardRange for any other type supporting opUnary!++"?
I think this is OK. It's just like map() returning an input range if you give it an input range, a forward range if you give it a forward range, etc.. Or joiner() returning a forward range only if you give it a forward range of a forward range, otherwise it's just an input range, even if one of the inner / outer ranges is forward (both the outer and inner range must be forward ranges, otherwise the result can't guarantee that .save will work correctly). Basically, return the best range you can without adding hidden costs (like O(n) methods), otherwise fall back to a more primitive range type. This rule is observed by other parts of Phobos too. T -- The richest man is not he who has the most, but he who needs the least.
Dec 23 2013
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Dec 23, 2013 at 03:00:25PM +0000, Francesco Cattoglio wrote:
 Sorry for the amount of text, but I tried to explain everything in a
 clear and simple way.
 I'm willing to volunteer for adding support for more types in iota.
 The relevant discussion is:
 https://d.puremagic.com/issues/show_bug.cgi?id=10762
 
 A few preliminary considerations:
 - iota() currently returns a Random Access range, and I'm sure
 nobody would agree to downgrade the result to a ForwardRange or an
 InputRange, because that would break an unknown amount of code.
Certainly, the new iota() implementation should not reduce current functionality, but only add to it.
 - I think everyone agrees that even after enhancements, iota()
 should always return a RA range, even if we use types that are
 currently not supported. It would make little sense returning
 different kind of ranges for different input types.
This is false. Phobos has a lot of code that returns slightly different types depending on what the input was. For example, .map returns a random access range if the input is random access, a bidirectional / forward / input range if that's that the input is, etc.. This is perfectly normal. It makes little sense to require, e.g., .map to always return, say, a forward range even if you hand it an input range -- it wouldn't be able to do this without introducing very inefficient code (like caching entries so that it can implement .save). Phobos range adaptors should always return the "best of input functionality", i.e., if the incoming range has .save, then where reasonable the resulting range also should have .save; ditto for opIndex, .back, .popBack, etc..
 Let's define the types: When calling iota(start,end,inc)
   S=typeof(start),
   E=typeof(end),
   I=typeof(inc),
   C=CommonType!(S,E).
 
 My proposal:
 iota(start, end, inc) accepts any type, as long as
     {C c; c += inc; c < end;} or {C c; c = c + inc; c < end;} is
 valid code;

 Since inc type might not be directly comparable to 0, we also check
 if (start + inc < start). If this returns true, this means that "inc
 is negative" in a more general sense.
I'm a bit uneasy about this, but I guess it's the price of completely generic code, since you're right, there's no guarantee the inc type is comparable to 0.
 We can use this information to return an empty range when needed,
 respecting the behaviour defined by the library reference. eg: (start
 < end && inc < 0) => return
 empty range.

 end is not required to be equal to (start + n*inc) for any given n;
 eg: iota(4, 9, 2) should be valid and return [4, 6, 8]. We can
 discuss if this makes sense or should be changed, but I think it
 would be better this way.
I think this way is better.
 If the code {int n; I n_inc = n * inc;} is valid, this instruction
 is used for providing O(1) access for opIndex and opSlice methods.
Yes.
 If the code {C c; c -= inc;} or {C c; c = c - inc} is valid, this
 instruction is used for providing O(1) access for popBack() method.
Yes.
 If no optimization is available, the code will provide O(n)
 performance for those methods.
No. If (start + n*inc) is not compilable, then iota should not be a random-access range. I don't like the idea that iota[n] is O(1) for some types and O(n) for other types.
 The real issue however is that construction of the range might end up
 taking O(n) time, because we have to provide the length and the back
 property. One work around is computing those lazily only if the
 user requests them.
No, if (start + n*inc) is not available, don't provide .length and don't provide .back. Otherwise you're adding unnecessary baggage in the returned range type for most code that don't care about .length or .back.
 By doing this, anyone only using iota() for forward iteration will
 still obtain O(1) performance.
 
 iota(start, end) accepts any type, as long as
     {C c; ++c; c < end;} or {iota(start, end, 1);} is valid code. If
 both forms are valid, the iota(start, end, 1) version is preferred
 (allowing possible optimizations as discussed before).
 Everything else ends up being the same as before: popBack() can be
 optimized if {--c;} is valid code, the opIndex, opSlice, back and
 length methods will take O(n) time, no way around this sadly.
No, we should not implement any O(n) time methods in iota. If only ++ is available in the base type, then .length, .back, opSlice, will not be available. Basically, if the user type only supports ++, then in normal user code they will not expect to compute length easily, or to be able jump to over several consecutive values. So chances are that they won't be using them with the range returned by iota either. So this will just be unneeded added complexity in the iota implementation. I vote against it.
 hsteoh suggested:
     If start+inc is *not* supported but start-- is, and end < start,
 should we support iota(start,end)?
 I think this idea should be discarded since some code could quickly
 become a minefield:
 type T implements ++t and --t;
 type P only implements ++p;
 t1 < t2 => iota(t2, t1) has a way to compute a non-empty range;
 p1 < p2 => iota(p2, p1) can do nothing but return an empty range;
 And this behaviour really smells bad, IMHO. The only way to solve
 this is requiring opUnary!"--" being implemented for the type to be
 used, and I am not sure about this (most iota uses only really need
 ++).
I think this part is optional, I won't miss it if it won't be not there, actually. I only suggested it because I thought it would be nice to support iota(a,b,-1) for types that don't have a way to specify inc. But like you said, it's probably very rare for people to actually want to do this.
 Any suggestion/critique? If this looks good to you, I can start
 working on it. If you disagree on something (and I know you have
 something to say!), discussion is more than welcome!
[...] I think overall it looks good, except for the parts where you try to implement .back, .length, opSlice, etc., when the underlying type doesn't support it. I think that's unnecessary work. Just as we don't expect sqrt() to return a meaningful value for -1 for real numbers, but we *do* expect a meaningful value for complex numbers, so there's no reason iota() must always return a RA range. If the user wants RA access, then he should implement more primitives in his type, it's not iota's job to do that for him. Another thing to be mindful of is the current existing overloads of iota. Your implementation should either be in distinct overloads from them (so that they continue to work as they do now), or it should subsume them and provide (at least) equivalent functionality, if not better. In no case should existing functionality be broken by the new replacement. This sounds obvious but may be harder than it appears, because there's an overload (or multiple overloads?) specifically for floating-point types, and you'll have to take into account the quirks of floating-point types to handle all the cases correctly. Keep in mind that if a float is too large, iota() may not be able to return a meaningful range (e.g., x+inc may not have a distinct floating-point representation from x when abs(x) is too big relative to inc). Also, what should be done if mathematically x + n*inc == end exactly, but due to roundoff error it misses by a few ulps. Then iota() may have different lengths depending on CPU (e.g. 80-bit real vs. 128-bit real), rounding flags, etc., and things could get hairy. You might want to keep the floating-point overload(s) of iota as-is to avoid having to deal with this mess. :) T -- One disk to rule them all, One disk to find them. One disk to bring them all and in the darkness grind them. In the Land of Redmond where the shadows lie. -- The Silicon Valley Tarot
Dec 23 2013
parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
Thank you everyone for the feedback. I made the wrong assumption 
about phobos design, I didn't knew that the policy here is "when 
needed, relax the range", and now I see it makes perfect sense.
The range will only be a RA range for types that implement (inc * 
n) and ((end - begin) / step) (used for lenght computation), 
otherwise it will be a ForwardRange, because it can't be 
directional if we can't compute the last element in O(1).

On Tuesday, 24 December 2013 at 01:42:21 UTC, H. S. Teoh wrote:
 there's
 an overload (or multiple overloads?) specifically for 
 floating-point
 types, and you'll have to take into account the quirks of 
 floating-point
 types to handle all the cases correctly.
 [...] You might want to keep the floating-point
 overload(s) of iota as-is to avoid having to deal with this 
 mess. :)
I actually think the current float doesn't behave perfectly either. I will not forget about float quirks, don't worry.
Ah, nice. There's an unstated assumption here - adding inc n 
times is the same as adding n * inc.
Right, completely missed that. I guess checking a few test cases at compile time is the best one can do. Checking for every n could take some infinite amount of time :P
No, there are types for which increment is sensible but not 
adding an arbitrary number.
I agree. After relaxing the range, we can prefer a specialized version over the iota(begin, end, 1) version. The latter should be used as a backup instead for cases where ++ is not implemented.
Not sure I understand this, but any reasoning that leads to the 
conclusion that simple ++ ranges should be discarded must be 
carefully revised.
Maybe I should have pasted all the suggestions from h.s. teoh, to make it more clear which one I didn't like. He suggested to add extra functionality if the type provides opUnary!--. ++ ranges will be supported. what will not be supported is extra functionality if -- is defined, because similar types used in the same case might produce different results.
Dec 24 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Francesco Cattoglio:

 I agree. After relaxing the range, we can prefer a specialized 
 version over the iota(begin, end, 1) version. The latter should 
 be used as a backup instead for cases where ++ is not 
 implemented.
One possible disadvantage is when you want an array of various iota (all of the same indexed type, like int) (currently this doesn't compile), this was a potential use case for me: void main() { import std.range: iota; auto intervals = [iota(10), iota(2, 7), iota(2, 15, 2)]; } Bye, bearophile
Dec 24 2013
parent "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Tuesday, 24 December 2013 at 10:44:54 UTC, bearophile wrote:
 Francesco Cattoglio:
 One possible disadvantage is when you want an array of various 
 iota (all of the same indexed type, like int) (currently this 
 doesn't compile), this was a potential use case for me:

 void main() {
     import std.range: iota;
     auto intervals = [iota(10), iota(2, 7), iota(2, 15, 2)];
 }

 Bye,
 bearophile
Nice point: the issue here is that every iota defines its own return type. I will see if there's some way around this on the library side. The "user side" workaround is simple: void main() { import std.range: iota; auto intervals = [iota(0, 10, 1), iota(2, 7, 1), iota(2, 15, 2)]; }
Dec 24 2013
prev sibling next sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Tuesday, 24 December 2013 at 10:38:17 UTC, Francesco Cattoglio 
wrote:
 The range will only be a RA range for types that implement (inc 
 * n) and ((end - begin) / step) (used for lenght computation), 
 otherwise it will be a ForwardRange, because it can't be 
 directional if we can't compute the last element in O(1).
Bidirectionality and random access are separate capabilities; the former can be supported without the latter through `--end`, and `end == start`, and we should support that. If it causes problems when the same range is traversed from both ends, then that is an issue with the UDT's operator overloads.
Dec 24 2013
next sibling parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Tuesday, 24 December 2013 at 11:05:05 UTC, Jakob Ovrum wrote:
 On Tuesday, 24 December 2013 at 10:38:17 UTC, Francesco 
 Cattoglio wrote:
 The range will only be a RA range for types that implement 
 (inc * n) and ((end - begin) / step) (used for lenght 
 computation), otherwise it will be a ForwardRange, because it 
 can't be directional if we can't compute the last element in 
 O(1).
Bidirectionality and random access are separate capabilities; the former can be supported without the latter through `--end`, and `end == start`, and we should support that. If it causes problems when the same range is traversed from both ends, then that is an issue with the UDT's operator overloads.
There's a catch: if we want bidirectional, we need the last element of the range. This means we have to choose one of the following 2: 1) make the assumption that the user choose an end that corresponds to the first element out of the range. 2) compute the last item by ourselves. 1) would be error prone: if the user fails to provide a correct entry, popping the back would give you values that differ from the ones you pop from the front. The user might also genuinely not know what the last element is (eg: you add 25 minutes to a given time, and you want the range to stop before midnight). 2) is not possible in O(1), unless we can divide by the step. We could provide bidirectionality if the type supports division but not multiplication. But I honestly can not see any use case for this. Unless I'm missing something that allows quick computation of the end using only += and comparison.
Dec 24 2013
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Tuesday, 24 December 2013 at 11:25:04 UTC, Francesco Cattoglio 
wrote:
 There's a catch: if we want bidirectional, we need the last 
 element of the range.
`end` is a parameter to all overloads of `iota`. Note that it is exclusive, so the first `back` is `--end`, not `end` as passed in by the caller. Are you sure you understand bidirectional ranges correctly? Any range that has the `back` property and `popBack` method are bidirectional.
Dec 24 2013
parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Tuesday, 24 December 2013 at 11:30:32 UTC, Jakob Ovrum wrote:
 On Tuesday, 24 December 2013 at 11:25:04 UTC, Francesco 
 Cattoglio wrote:
 There's a catch: if we want bidirectional, we need the last 
 element of the range.
Are you sure you understand bidirectional ranges correctly? Any range that has the `back` property and `popBack` method are bidirectional.
Correct, but there's no way to compute "back" with less than O(n) complexity, unless division by increment is available. (Actually, I think we can achieve O(log n) with multiplication alone, but I think it might be lots of work with very little benefits) I should have specified better: we need to provide `back', and Andrei suggested that no primitive should be more than complex than O(1).
Dec 24 2013
next sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Tuesday, 24 December 2013 at 11:47:12 UTC, Francesco Cattoglio 
wrote:
 Correct, but there's no way to compute "back" with less than 
 O(n) complexity, unless division by increment is available. 
 (Actually, I think we can achieve O(log n) with multiplication 
 alone, but I think it might be lots of work with very little 
 benefits)
 I should have specified better: we need to provide `back', and 
 Andrei suggested that no primitive should be more than complex 
 than O(1).
Implement `back` is really trivial. Simplified example: --- auto iota(T)(T start, T end) { static struct Result { T start, end; bool empty() property { return start == end; } T front() property { return start; } void popFront() { ++start; } T back() property { return end; } void popBack() { --end; } // etc } return Result(start, --end); } ---
Dec 24 2013
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 24 December 2013 at 11:57:04 UTC, Jakob Ovrum wrote:
 On Tuesday, 24 December 2013 at 11:47:12 UTC, Francesco 
 Cattoglio wrote:
 Correct, but there's no way to compute "back" with less than 
 O(n) complexity, unless division by increment is available. 
 (Actually, I think we can achieve O(log n) with multiplication 
 alone, but I think it might be lots of work with very little 
 benefits)
 I should have specified better: we need to provide `back', and 
 Andrei suggested that no primitive should be more than complex 
 than O(1).
Implement `back` is really trivial. Simplified example: --- auto iota(T)(T start, T end) { static struct Result { T start, end; bool empty() property { return start == end; } T front() property { return start; } void popFront() { ++start; } T back() property { return end; } void popBack() { --end; } // etc } return Result(start, --end); } ---
I think you are missing the point of what happens if the step is not 1 (or if the passed in type can have fractional input). EG: iota(0, 105, 10); or iota(0, 10.5); In this case, "back" should be 100, and not 95. To compute back, you need to be able to evaluate length, and to add length*inc to front.
Dec 24 2013
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 24/12/13 13:58, monarch_dodra wrote:
 I think you are missing the point of what happens if the step is not 1 (or if
 the passed in type can have fractional input). EG:

 iota(0, 105, 10);
 or
 iota(0, 10.5);

 In this case, "back" should be 100, and not 95. To compute back, you need to be
 able to evaluate length, and to add length*inc to front.
Oh, snap. Have we been working on the same problems for too long? :-)
Dec 24 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
 On 24/12/13 13:58, monarch_dodra wrote:
 I think you are missing the point of what happens if the step is not 1
 (or if
 the passed in type can have fractional input). EG:

 iota(0, 105, 10);
 or
 iota(0, 10.5);

 In this case, "back" should be 100, and not 95. To compute back, you
 need to be
 able to evaluate length, and to add length*inc to front.
Oh, snap. Have we been working on the same problems for too long? :-)
The integral cases are easy. We need to crack the floating point case: given numbers low, up, and step, what's the closest number smaller than up that's reached by repeated adds of step to low? Andrei
Dec 24 2013
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 24, 2013 at 09:10:53AM -0800, Andrei Alexandrescu wrote:
 On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
On 24/12/13 13:58, monarch_dodra wrote:
I think you are missing the point of what happens if the step is not
1 (or if the passed in type can have fractional input). EG:

iota(0, 105, 10);
or
iota(0, 10.5);

In this case, "back" should be 100, and not 95. To compute back, you
need to be able to evaluate length, and to add length*inc to front.
Oh, snap. Have we been working on the same problems for too long? :-)
The integral cases are easy. We need to crack the floating point case: given numbers low, up, and step, what's the closest number smaller than up that's reached by repeated adds of step to low?
[...] The closest number is simply step*floor((up-low)/step). There's probably a better way to write that expression that avoids bad roundoff errors, though. T -- Why can't you just be a nonconformist like everyone else? -- YHL
Dec 24 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 24, 2013 at 09:27:54AM -0800, H. S. Teoh wrote:
 On Tue, Dec 24, 2013 at 09:10:53AM -0800, Andrei Alexandrescu wrote:
 On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
On 24/12/13 13:58, monarch_dodra wrote:
I think you are missing the point of what happens if the step is not
1 (or if the passed in type can have fractional input). EG:

iota(0, 105, 10);
or
iota(0, 10.5);

In this case, "back" should be 100, and not 95. To compute back,
you need to be able to evaluate length, and to add length*inc to
front.
Oh, snap. Have we been working on the same problems for too long? :-)
The integral cases are easy. We need to crack the floating point case: given numbers low, up, and step, what's the closest number smaller than up that's reached by repeated adds of step to low?
[...] The closest number is simply step*floor((up-low)/step). There's probably a better way to write that expression that avoids bad roundoff errors, though.
[...] Maybe (up - fmod((up-low), step)) might be better? I'm not 100% sure. T -- VI = Visual Irritation
Dec 24 2013
prev sibling parent reply "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
wrote:
 On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
 On 24/12/13 13:58, monarch_dodra wrote:
 I think you are missing the point of what happens if the step 
 is not 1
 (or if
 the passed in type can have fractional input). EG:

 iota(0, 105, 10);
 or
 iota(0, 10.5);

 In this case, "back" should be 100, and not 95. To compute 
 back, you
 need to be
 able to evaluate length, and to add length*inc to front.
Oh, snap. Have we been working on the same problems for too long? :-)
The integral cases are easy. We need to crack the floating point case: given numbers low, up, and step, what's the closest number smaller than up that's reached by repeated adds of step to low? Andrei
Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
Dec 24 2013
next sibling parent reply "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
On Tuesday, 24 December 2013 at 18:56:02 UTC, Craig Dillabaugh
wrote:
 On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei 
 Alexandrescu
 wrote:
 On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
clip
 Doesn't think work, or am I missing something?

 low + floor( (up-low)/step ) * step
I meant "Doesn't this work". Why can't I ever make a post without a typo!
Dec 24 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 24, 2013 at 06:57:50PM +0000, Craig Dillabaugh wrote:
 On Tuesday, 24 December 2013 at 18:56:02 UTC, Craig Dillabaugh
 wrote:
On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
wrote:
On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
clip
Doesn't think work, or am I missing something?

low + floor( (up-low)/step ) * step
I meant "Doesn't this work". Why can't I ever make a post without a typo!
You mean, a tpyo? :-P T -- No! I'm not in denial!
Dec 24 2013
parent reply "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
On Tuesday, 24 December 2013 at 19:08:40 UTC, H. S. Teoh wrote:
 On Tue, Dec 24, 2013 at 06:57:50PM +0000, Craig Dillabaugh 
 wrote:
 On Tuesday, 24 December 2013 at 18:56:02 UTC, Craig Dillabaugh
 wrote:
On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei 
Alexandrescu
wrote:
On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
clip
Doesn't think work, or am I missing something?

low + floor( (up-low)/step ) * step
I meant "Doesn't this work". Why can't I ever make a post without a typo!
You mean, a tpyo? :-P T
Exactly!
Dec 24 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/24/13 11:17 AM, Craig Dillabaugh wrote:
 On Tuesday, 24 December 2013 at 19:08:40 UTC, H. S. Teoh wrote:
 On Tue, Dec 24, 2013 at 06:57:50PM +0000, Craig Dillabaugh wrote:
 On Tuesday, 24 December 2013 at 18:56:02 UTC, Craig Dillabaugh
 wrote:
On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei >Alexandrescu
wrote:
On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
clip
Doesn't think work, or am I missing something?

low + floor( (up-low)/step ) * step
I meant "Doesn't this work". Why can't I ever make a post without a typo!
You mean, a tpyo? :-P T
Exactly!
Use a spellchequer. Andrei
Dec 24 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/24/13 10:56 AM, Craig Dillabaugh wrote:
 On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
 wrote:
 On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
 On 24/12/13 13:58, monarch_dodra wrote:
 I think you are missing the point of what happens if the step is not 1
 (or if
 the passed in type can have fractional input). EG:

 iota(0, 105, 10);
 or
 iota(0, 10.5);

 In this case, "back" should be 100, and not 95. To compute back, you
 need to be
 able to evaluate length, and to add length*inc to front.
Oh, snap. Have we been working on the same problems for too long? :-)
The integral cases are easy. We need to crack the floating point case: given numbers low, up, and step, what's the closest number smaller than up that's reached by repeated adds of step to low? Andrei
Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account. Andrei
Dec 24 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote:
 On 12/24/13 10:56 AM, Craig Dillabaugh wrote:
On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
wrote:
[.[..]
The integral cases are easy. We need to crack the floating point
case: given numbers low, up, and step, what's the closest number
smaller than up that's reached by repeated adds of step to low?

Andrei
Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.
[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.) T -- Only boring people get bored. -- JM
Dec 24 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/24/13 11:59 AM, H. S. Teoh wrote:
 On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote:
 On 12/24/13 10:56 AM, Craig Dillabaugh wrote:
 On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
 wrote:
[.[..]
 The integral cases are easy. We need to crack the floating point
 case: given numbers low, up, and step, what's the closest number
 smaller than up that's reached by repeated adds of step to low?

 Andrei
Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.
[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.)
No, again, I think nothing like that would work. It's hopelessly naive (in addition to being plain wrong for simple inputs like low=1, high=10, step=1). There are combinations of low, high, and step that don't even make progress, i.e. step is sufficiently small compared to low to effectively make low + step == low. Try this to verify approaches: #!/Users/aalexandre/bin/rdmd import std.stdio, std.conv, std.math; void main(string[] args) { auto low = to!double(args[1]); auto up = to!double(args[2]); auto step = to!double(args[3]); writeln("Predicted: ", low + fmod(up-low, step)*step); for (;;) { auto next = low + step; if (next >= up) break; low = next; } writeln("Actual: ", low); } Andrei
Dec 24 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 24, 2013 at 12:57:02PM -0800, Andrei Alexandrescu wrote:
 On 12/24/13 11:59 AM, H. S. Teoh wrote:
On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote:
On 12/24/13 10:56 AM, Craig Dillabaugh wrote:
On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
wrote:
[...]
The integral cases are easy. We need to crack the floating point
case: given numbers low, up, and step, what's the closest number
smaller than up that's reached by repeated adds of step to low?

Andrei
Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.
[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.)
No, again, I think nothing like that would work. It's hopelessly naive (in addition to being plain wrong for simple inputs like low=1, high=10, step=1). There are combinations of low, high, and step that don't even make progress, i.e. step is sufficiently small compared to low to effectively make low + step == low.
Then what should be returned in that case?
 Try this to verify approaches:
 
 #!/Users/aalexandre/bin/rdmd
 import std.stdio, std.conv, std.math;
 
 void main(string[] args)
 {
     auto low = to!double(args[1]);
     auto up = to!double(args[2]);
     auto step = to!double(args[3]);
     writeln("Predicted: ", low + fmod(up-low, step)*step);
     for (;;)
     {
         auto next = low + step;
Aren't you accumulating roundoff errors here? Since + may introduce an error of 1/2 ulp, if your loop runs in n steps, wouldn't it accumulate an error of n/2 ulps? For large n, this would significantly skew your results.
         if (next >= up) break;
         low = next;
     }
     writeln("Actual: ", low);
 }
[...] T -- All problems are easy in retrospect.
Dec 24 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/24/13 1:09 PM, H. S. Teoh wrote:
 On Tue, Dec 24, 2013 at 12:57:02PM -0800, Andrei Alexandrescu wrote:
 On 12/24/13 11:59 AM, H. S. Teoh wrote:
 On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote:
 On 12/24/13 10:56 AM, Craig Dillabaugh wrote:
 On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
 wrote:
[...]
 The integral cases are easy. We need to crack the floating point
 case: given numbers low, up, and step, what's the closest number
 smaller than up that's reached by repeated adds of step to low?

 Andrei
Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.
[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.)
No, again, I think nothing like that would work. It's hopelessly naive (in addition to being plain wrong for simple inputs like low=1, high=10, step=1). There are combinations of low, high, and step that don't even make progress, i.e. step is sufficiently small compared to low to effectively make low + step == low.
Then what should be returned in that case?
The same as an iota with step zero.
          auto next = low + step;
Aren't you accumulating roundoff errors here?
Ideally one addition is all needed for popBack. Andrei
Dec 24 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 24, 2013 at 01:18:34PM -0800, Andrei Alexandrescu wrote:
 On 12/24/13 1:09 PM, H. S. Teoh wrote:
On Tue, Dec 24, 2013 at 12:57:02PM -0800, Andrei Alexandrescu wrote:
On 12/24/13 11:59 AM, H. S. Teoh wrote:
On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote:
On 12/24/13 10:56 AM, Craig Dillabaugh wrote:
On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
wrote:
[...]
The integral cases are easy. We need to crack the floating point
case: given numbers low, up, and step, what's the closest number
smaller than up that's reached by repeated adds of step to low?

Andrei
Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.
[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.)
No, again, I think nothing like that would work. It's hopelessly naive (in addition to being plain wrong for simple inputs like low=1, high=10, step=1). There are combinations of low, high, and step that don't even make progress, i.e. step is sufficiently small compared to low to effectively make low + step == low.
Then what should be returned in that case?
The same as an iota with step zero.
         auto next = low + step;
Aren't you accumulating roundoff errors here?
Ideally one addition is all needed for popBack.
[...] You're missing my point. I'm not talking about popBack specifically here. I'm talking about the problem of accumulated roundoff error in the implementation of iota. You're suggesting that iota should keep a running accumulator representing the current value of .front, and popFront should simply add step to this accumulator. But this kind of implementation is problematic, because it accumulates roundoff errors. Suppose evaluating current + step introduces a roundoff error of E. Then the next time we call popFront, the error becomes 2*E. Then the third time the error becomes 3*E. So after calling popFront n times, the accumulator is now off from the correct value by n*E. Since n is increasing, eventually n*E > step, which will cause iota to return the wrong number of elements in the range (not to mention that the last few elements will be completely inaccurate). Yet you're suggesting to use this method of incrementally adding step to an accumulator as the standard by which to verify the correctness of .back? That makes no sense. The only floating-point implementation of iota that guarantees the correct number of iterations (up to floating-point precision, of course) is one that *directly* calculates the value of front_i = low + i*step, instead of consecutively adding step to an accumulator, no matter whether you're calling popFront or popBack or opIndex. T -- The fact that anyone still uses AOL shows that even the presence of options doesn't stop some people from picking the pessimal one. - Mike Ellis
Dec 24 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/24/13 3:11 PM, H. S. Teoh wrote:
 You're missing my point.
It's Christmas, let's be nice to one another :o). The only problem here is that I didn't explain my point enough, which fostered confusion.
 I'm not talking about popBack specifically
 here. I'm talking about the problem of accumulated roundoff error in the
 implementation of iota. You're suggesting that iota should keep a
 running accumulator representing the current value of .front, and
 popFront should simply add step to this accumulator.

 But this kind of implementation is problematic, because it accumulates
 roundoff errors.
No need to explain. I understand all of this already.
 Yet you're suggesting to use this method of incrementally adding step to
 an accumulator as the standard by which to verify the correctness of
 .back? That makes no sense.
Of course it does. It's just that it's quite a difficult problem. The current implementation is conservative at the expense of speed.
 The only floating-point implementation of iota that guarantees the
 correct number of iterations (up to floating-point precision, of course)
 is one that *directly* calculates the value of front_i = low + i*step,
 instead of consecutively adding step to an accumulator, no matter
 whether you're calling popFront or popBack or opIndex.
No. Consider: struct IotaDouble { private: double begin, end, step, current; size_t index; enum UpdateMethod { indexed, addition, increment } UpdateMethod m; UpdateMethod initUpdate() { ... this is the difficult part ... } ... void popFront() { final switch (m) { case UpdateMethod.indexed: current = begin + ++index * step; break; case UpdateMethod.addition: current += step; break; case UpdateMethod.increment: ++current; break; } } } I suspect increment is not much faster than addition, so they could be merged subject to measurement. But I think the addition is quite a bit faster than indexing, which makes it worth special casing for. Also, the update method will be invariant through the lifetime of the object, which will play well with the branch predictor (the test may come at virtually or literally no cost). The difficulty, of course, is choosing the appropriate update method depending on the limits and step. Andrei
Dec 24 2013
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 24/12/13 12:57, Jakob Ovrum wrote:
 Implement `back` is really trivial.

 Simplified example:
 ---
 auto iota(T)(T start, T end)
 {
      static struct Result
      {
          T start, end;

          bool empty()  property { return start == end; }
          T front()  property { return start; }
          void popFront() { ++start; }
          T back()  property { return end; }
          void popBack() { --end; }
          // etc
      }

      return Result(start, --end);
 }
Complication: as it stands, iota is defined as an open interval; its values consist of start, start + delta, start + 2*delta, ..., start + n*delta ... where n is the largest possible value of n such that start + n*delta < end. It's NOT however guaranteed that start + n*delta == end - delta. Consider: iota(0.0, 0.91, 0.1) // gives 0.0, 0.1, ..., 0.8, 0.9 So, absent the ability to calculate start + n*delta in O(1), it's _not_ trivial to calculate the initial value of .back.
Dec 24 2013
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 24, 2013 at 11:57:03AM +0000, Jakob Ovrum wrote:
 On Tuesday, 24 December 2013 at 11:47:12 UTC, Francesco Cattoglio
 wrote:
Correct, but there's no way to compute "back" with less than O(n)
complexity, unless division by increment is available. (Actually,
I think we can achieve O(log n) with multiplication alone, but I
think it might be lots of work with very little benefits)
I should have specified better: we need to provide `back', and
Andrei suggested that no primitive should be more than complex
than O(1).
Implement `back` is really trivial. Simplified example: --- auto iota(T)(T start, T end) { static struct Result { T start, end; bool empty() property { return start == end; } T front() property { return start; } void popFront() { ++start; } T back() property { return end; } void popBack() { --end; } // etc } return Result(start, --end); } ---
This code is wrong for iota(1.0, 9.5), because .back must be of the form start + n*step for some integer n, but in this case end is not an integral multiple of step away from start. (It's not only wrong for .back, it also won't terminate because start==end will never hold.) T -- I think the conspiracy theorists are out to get us...
Dec 24 2013
parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Tuesday, 24 December 2013 at 15:41:06 UTC, H. S. Teoh wrote:
 This code is wrong for iota(1.0, 9.5), because .back must be of 
 the form
 start + n*step for some integer n, but in this case end is not 
 an
 integral multiple of step away from start. (It's not only wrong 
 for
 .back, it also won't terminate because start==end will never 
 hold.)
It is a simplified example. It has no pretence of handling floating point.
Dec 28 2013
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 24/12/13 16:39, H. S. Teoh wrote:
 This code is wrong for iota(1.0, 9.5), because .back must be of the form
 start + n*step for some integer n, but in this case end is not an
 integral multiple of step away from start. (It's not only wrong for
 .back, it also won't terminate because start==end will never hold.)
I don't see the reason why there needs to be a start == end condition -- surely start >= end will suffice?
Dec 24 2013
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/24/13 3:57 AM, Jakob Ovrum wrote:
          bool empty()  property { return start == end; }
This is better start >= end if ordering comparisons are supported. Andrei
Dec 24 2013
prev sibling parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Tuesday, 24 December 2013 at 11:47:12 UTC, Francesco Cattoglio 
wrote:
 Correct, but there's no way to compute "back" with less than 
 O(n) complexity, unless division by increment is available.
I would like to add that I want to compute back because the current documentation states: Returns a range that goes through the numbers begin, begin + step, begin + 2 * step, ..., up to and excluding end. Up to and excluding seems perfectly reasonable, and others have agreed that allowing the user to write iota(4, 9, 2) can be a nice idea. Another nice example: iota(DateTime(2012, 1, 1), DateTime(2013, 1, 1), dur!"days"(5)); can you easily tell what is the "back" element?
Dec 24 2013
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Tuesday, 24 December 2013 at 12:02:54 UTC, Francesco Cattoglio 
wrote:
 iota(DateTime(2012, 1, 1), DateTime(2013, 1, 1), dur!"days"(5));
 can you easily tell what is the "back" element?
If it can't be defined reasonably for a custom step[1], then simply don't support it when a custom step is provided. There's absolutely no reason for this to compromise the functionality of the common case. [1] Which I'm not convinced of; e.g. `back` == `DateTime(2013, 1, 1) - dur!"days"(5)`.
Dec 28 2013
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 28/12/13 09:06, Jakob Ovrum wrote:
 [1] Which I'm not convinced of; e.g. `back` == `DateTime(2013, 1, 1) -
 dur!"days"(5)`.
Are you sure that's going to work if the iota covers a leap year? :-)
Dec 28 2013
next sibling parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Saturday, 28 December 2013 at 12:16:32 UTC, Joseph Rushton 
Wakeling wrote:
 On 28/12/13 09:06, Jakob Ovrum wrote:
 [1] Which I'm not convinced of; e.g. `back` == `DateTime(2013, 
 1, 1) -
 dur!"days"(5)`.
Are you sure that's going to work if the iota covers a leap year? :-)
And that's exactly the reason I choose 2012 as an example :D
Dec 28 2013
parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 28/12/13 14:16, Francesco Cattoglio wrote:
 And that's exactly the reason I choose 2012 as an example :D
It's going to get fun if we have to start taking into account leap seconds too ;-) On a serious note -- I wouldn't worry about what kind of range type you generate with iota. It'll be fine to implement iota for a new type starting with an input (or more likely, forward) range, and add random-access functionality later as and where it's possible.
Dec 28 2013
prev sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 28 December 2013 at 12:16:32 UTC, Joseph Rushton 
Wakeling wrote:
 Are you sure that's going to work if the iota covers a leap 
 year? :-)
How would it fail? std.datetime does a good job with leap years AFAIK.
Dec 28 2013
next sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 28/12/13 14:58, Jakob Ovrum wrote:
 How would it fail? std.datetime does a good job with leap years AFAIK.
Try the attached code. The largest value of DateTime(2012, 1, 1) + dur!"days"(5 * n) that is less than DateTime(2013, 1, 1) is _not_ DateTime(2013, 1, 1) - dur!"days"(5). :-)
Dec 28 2013
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 28 December 2013 at 14:09:17 UTC, Joseph Rushton 
Wakeling wrote:
 Try the attached code.  The largest value of DateTime(2012, 1, 
 1) + dur!"days"(5
 * n) that is less than DateTime(2013, 1, 1) is _not_ 
 DateTime(2013, 1, 1) -
 dur!"days"(5). :-)
OK, so this has nothing to do with leap years, but that 5.days is an improper step.
Dec 28 2013
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 28/12/13 17:10, Jakob Ovrum wrote:
 OK, so this has nothing to do with leap years, but that 5.days is an improper
step.
Oh, I see -- you're assuming that iota has to be defined with start, end and step such that end = start + (n * step) for some integer n >= 0. I can see the case for it, but to me it seems like a too restrictive requirement.
Dec 28 2013
parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 28 December 2013 at 16:30:27 UTC, Joseph Rushton 
Wakeling wrote:
 I can see the case for it, but to me it seems like a too 
 restrictive requirement.
Yes, I can totally see that. I'm not really invested either way, because while I see a need for bidirectionality with `iota(start, end)`, it seems less useful with `iota(start, end, step)`.
Dec 28 2013
prev sibling parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Saturday, 28 December 2013 at 13:58:40 UTC, Jakob Ovrum wrote:
 On Saturday, 28 December 2013 at 12:16:32 UTC, Joseph Rushton 
 Wakeling wrote:
 Are you sure that's going to work if the iota covers a leap 
 year? :-)
How would it fail? std.datetime does a good job with leap years AFAIK.
Yes it does, the catch is: 2012, Jan, 1 + "365 days") = 2012, Dec, 31 because 2012 is a leap year. If you compute "back = end - duration", you are asserting the user will always enter correct bounds. This is fine for trivial intervals, but iota won't be usable anywhere else. It's always the same "issue": you have to compute the last element inside iota, you should never rely on the user giving you ideal inputs.
Dec 28 2013
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 28 December 2013 at 14:13:08 UTC, Francesco 
Cattoglio wrote:
 It's always the same "issue": you have to compute the last 
 element inside iota, you should never rely on the user giving 
 you ideal inputs.
Alright, so require division for bidirectionality when given a custom step. There's no reason division should be required for bidirectionality in the most common case of iota(start, end).
Dec 28 2013
parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Saturday, 28 December 2013 at 16:13:45 UTC, Jakob Ovrum wrote:
 Alright, so require division for bidirectionality when given a 
 custom step. There's no reason division should be required for 
 bidirectionality in the most common case of iota(start, end).
Ok, now I finally get your point. It goes something along the lines of: "if no step is provided, then we can assume end can be reached by just stepping forward (incrementing by one)". It makes sense, but personally I don't like to make assumptions. I think assumptions in library code are one of the worst sources of nasty bugs in user code.
Dec 28 2013
parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 28 December 2013 at 19:22:25 UTC, Francesco 
Cattoglio wrote:
 On Saturday, 28 December 2013 at 16:13:45 UTC, Jakob Ovrum 
 wrote:
 Alright, so require division for bidirectionality when given a 
 custom step. There's no reason division should be required for 
 bidirectionality in the most common case of iota(start, end).
Ok, now I finally get your point. It goes something along the lines of: "if no step is provided, then we can assume end can be reached by just stepping forward (incrementing by one)". It makes sense, but personally I don't like to make assumptions. I think assumptions in library code are one of the worst sources of nasty bugs in user code.
As long as `start < end` is true in the beginning, that's a perfectly reasonable assumption to make, especially if "end can be reached" means `start >= end` is true after some `n` number of increments. If we can't make any assumptions about the chosen concept primitives then they're no good as primitives at all.
Dec 28 2013
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 24 December 2013 at 11:05:05 UTC, Jakob Ovrum wrote:
 On Tuesday, 24 December 2013 at 10:38:17 UTC, Francesco 
 Cattoglio wrote:
 The range will only be a RA range for types that implement 
 (inc * n) and ((end - begin) / step) (used for lenght 
 computation), otherwise it will be a ForwardRange, because it 
 can't be directional if we can't compute the last element in 
 O(1).
Bidirectionality and random access are separate capabilities; the former can be supported without the latter through.
Actually, if the range is infinite, then you can also have RA without bidirectionality.
Dec 24 2013
prev sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 24/12/13 11:38, Francesco Cattoglio wrote:
 Ah, nice. There's an unstated assumption here - adding inc n times is the same
 as adding n * inc.
Right, completely missed that. I guess checking a few test cases at compile time is the best one can do. Checking for every n could take some infinite amount of time :P
Example case: iota(x, y, (x - y) / N) ... where x and y are floating point and N is anything other than a power of 2. You will probably wind up with cases where you get an unexpected extra point on the end that is (x - y - tinyEpsilon). DMD may be more prone to this than GDC/LDC. I once ran into a very amusing error with DMD (not using iota) when I tried to traverse the closed interval [0.0, 1.0] in increments of 0.1.
Dec 24 2013
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/23/13 7:00 AM, Francesco Cattoglio wrote:
 A few preliminary considerations:
 - iota() currently returns a Random Access range, and I'm sure nobody
 would agree to downgrade the result to a ForwardRange or an InputRange,
 because that would break an unknown amount of code.
Agreed.
 - I think everyone agrees that even after enhancements, iota() should
 always return a RA range, even if we use types that are currently not
 supported. It would make little sense returning different kind of ranges
 for different input types.
I think it makes a lot of sense to relax that. Different types have different properties leading to different iota capabilities.
 Let's define the types: When calling iota(start,end,inc)
    S=typeof(start),
    E=typeof(end),
    I=typeof(inc),
    C=CommonType!(S,E).

 My proposal:
 iota(start, end, inc) accepts any type, as long as
      {C c; c += inc; c < end;} or {C c; c = c + inc; c < end;} is valid
 code;
Sounds good. That's not sufficient to make it random access though.
 Since inc type might not be directly comparable to 0, we also check if
 (start + inc < start). If this returns true, this means that "inc is
 negative" in a more general sense. We can use this information to return
 an empty range when needed, respecting the behaviour defined by the
 library reference. eg: (start < end && inc < 0) => return empty range.
 end is not required to be equal to (start + n*inc) for any given n; eg:
 iota(4, 9, 2) should be valid and return [4, 6, 8]. We can discuss if
 this makes sense or should be changed, but I think it would be better
 this way.
Anything sensible is fine so long as we don't pay every iteration.
 If the code {int n; I n_inc = n * inc;} is valid, this instruction is
 used for providing O(1) access for opIndex and opSlice methods.
Ah, nice. There's an unstated assumption here - adding inc n times is the same as adding n * inc.
 If the code {C c; c -= inc;} or {C c; c = c - inc} is valid, this
 instruction is used for providing O(1) access for popBack() method.
Noice.
 If no optimization is available, the code will provide O(n) performance
 for those methods.
I don't think any primitive should be O(n).
 The real issue however is that construction of the range might end up
 taking O(n) time, because we have to provide the length and the back
 property. One work around is computing those lazily only if the user
 requests them.
 By doing this, anyone only using iota() for forward iteration will still
 obtain O(1) performance.
All primitives must be O(1).
 iota(start, end) accepts any type, as long as
      {C c; ++c; c < end;} or {iota(start, end, 1);} is valid code. If
 both forms are valid, the iota(start, end, 1) version is preferred
 (allowing possible optimizations as discussed before).
No, there are types for which increment is sensible but not adding an arbitrary number. (Impractical example: Peano arithmetic. Practical examples anyone?) So iota(start, end) should be a special range, not derived from the general one. Also x++ is faster than x += a where a is a variable.
 Everything else ends up being the same as before: popBack() can be
 optimized if {--c;} is valid code, the opIndex, opSlice, back and length
 methods will take O(n) time, no way around this sadly.
Must be O(1) or don't implement. This is the D way.
 hsteoh suggested:
      If start+inc is *not* supported but start-- is, and end < start,
 should we support iota(start,end)?
Absolutely.
 I think this idea should be discarded since some code could quickly
 become a minefield:
 type T implements ++t and --t;
 type P only implements ++p;
 t1 < t2 => iota(t2, t1) has a way to compute a non-empty range;
 p1 < p2 => iota(p2, p1) can do nothing but return an empty range;
 And this behaviour really smells bad, IMHO. The only way to solve this
 is requiring opUnary!"--" being implemented for the type to be used, and
 I am not sure about this (most iota uses only really need ++).
Not sure I understand this, but any reasoning that leads to the conclusion that simple ++ ranges should be discarded must be carefully revised. Andrei
Dec 23 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Francesco Cattoglio:

 Sorry for the amount of text, but I tried to explain everything 
 in a clear and simple way.
 I'm willing to volunteer for adding support for more types in 
 iota.
Probably directly addressed by issue 10762: Problem with iota(long) https://d.puremagic.com/issues/show_bug.cgi?id=6446 iota(BigInt) too https://d.puremagic.com/issues/show_bug.cgi?id=6447 assertion failure in std.range.iota https://d.puremagic.com/issues/show_bug.cgi?id=6531 iota should generate char intervals too https://d.puremagic.com/issues/show_bug.cgi?id=9447 But if you rewrite iota() also take in account the following: Purity: Make std.range.iota strongly pure https://d.puremagic.com/issues/show_bug.cgi?id=5746 map, filter, iota and zip in pure (and nothrow) functions https://d.puremagic.com/issues/show_bug.cgi?id=8882 An important enhancement: Optional "[]" syntax for std.range.iota too https://d.puremagic.com/issues/show_bug.cgi?id=10466 (A less important enhancement is issue 11252). Bye, bearophile
Dec 25 2013
parent reply "Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:
On Wednesday, 25 December 2013 at 10:58:53 UTC, bearophile wrote:
 Probably directly addressed by issue 10762:
 [snip]
 But if you rewrite iota() also take in account the following:
 [snip again]
 An important enhancement:

 Optional "[]" syntax for std.range.iota too
Wow! That's a lot of stuff needing work. Now I understand why some people were waiting for a better iota :D Everything seems reasonable, and the "[]" syntax could be a nice addition, too. Shouldn't be that much difficult.
 (A less important enhancement is issue 11252).
On the other hand, I have honestly no idea whatsoever about how to implement this
 Bye,
 bearophile
I will probably start working a bit tomorrow, and I guess I will leave the current float specialization untouched, at least at the beginning. In the mean time, merry Christmas to everyone!
Dec 25 2013
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Dec 25, 2013 at 02:30:45PM +0000, Francesco Cattoglio wrote:
 On Wednesday, 25 December 2013 at 10:58:53 UTC, bearophile wrote:
[...]
(A less important enhancement is issue 11252).
On the other hand, I have honestly no idea whatsoever about how to implement this
[...] It should only be supported for numeric types (i.e., that support +, *, /). Here's a crude attempt at it: struct Iota(S,T,U) { S start; T end; U step; ... // other stuff here bool opBinaryRight(string op)(V val) if (op=="in" && is(V.init < S.init) && is((V.init - S.init) % U.init) && is(T.init >= V.init)) { if (val < start || val >= end) return false; // Surprisingly, x%y actually appears to work // like fmod(x,y) in D for floating point types! // Not sure how to represent 0 in a generic way // though. return ((val - start) % step == 0); } } T -- What is Matter, what is Mind? Never Mind, it doesn't Matter.
Dec 27 2013
prev sibling parent Iain Buclaw <ibuclaw gdcproject.org> writes:
On 27 Dec 2013 20:33, "H. S. Teoh" <hsteoh quickfur.ath.cx> wrote:
 On Wed, Dec 25, 2013 at 02:30:45PM +0000, Francesco Cattoglio wrote:
 On Wednesday, 25 December 2013 at 10:58:53 UTC, bearophile wrote:
[...]
(A less important enhancement is issue 11252).
On the other hand, I have honestly no idea whatsoever about how to implement this
[...] It should only be supported for numeric types (i.e., that support +, *, /). Here's a crude attempt at it: struct Iota(S,T,U) { S start; T end; U step; ... // other stuff here bool opBinaryRight(string op)(V val) if (op=="in" && is(V.init < S.init) && is((V.init - S.init) % U.init) && is(T.init >= V.init)) { if (val < start || val >= end) return false; // Surprisingly, x%y actually appears to work // like fmod(x,y) in D for floating point types! // Not sure how to represent 0 in a generic way // though. return ((val - start) % step == 0); } }
For GDC, 'appears to work like' gets turned into 'it calls' fmod(x, y) in D. :)
Dec 29 2013