digitalmars.D - std.range.iota enhancement: supporting more types (AKA issue 10762)
- Francesco Cattoglio (70/70) Dec 23 2013 Sorry for the amount of text, but I tried to explain everything
- bearophile (7/16) Dec 23 2013 If the new iota accepts new types, then no existing code is using
- Francesco Cattoglio (6/10) Dec 23 2013 I do realize this, but I don't really like having iota()
- bearophile (6/7) Dec 23 2013 Other things in Phobos work like this. Usually in Phobos Big-O
- H. S. Teoh (14/25) Dec 23 2013 I think this is OK. It's just like map() returning an input range if you
- H. S. Teoh (71/142) Dec 23 2013 Certainly, the new iota() implementation should not reduce current
- Francesco Cattoglio (23/39) Dec 24 2013 Thank you everyone for the feedback. I made the wrong assumption
- bearophile (10/14) Dec 24 2013 One possible disadvantage is when you want an array of various
- Francesco Cattoglio (9/19) Dec 24 2013 Nice point: the issue here is that every iota defines its own
- Jakob Ovrum (7/11) Dec 24 2013 Bidirectionality and random access are separate capabilities; the
- Francesco Cattoglio (17/29) Dec 24 2013 There's a catch: if we want bidirectional, we need the last
- Jakob Ovrum (8/10) Dec 24 2013 `end` is a parameter to all overloads of `iota`. Note that it is
- Francesco Cattoglio (8/15) Dec 24 2013 Correct, but there's no way to compute "back" with less than O(n)
- Jakob Ovrum (20/28) Dec 24 2013 Implement `back` is really trivial.
- monarch_dodra (9/37) Dec 24 2013 I think you are missing the point of what happens if the step is
- Joseph Rushton Wakeling (2/9) Dec 24 2013 Oh, snap. Have we been working on the same problems for too long? :-)
- Andrei Alexandrescu (5/18) Dec 24 2013 The integral cases are easy. We need to crack the floating point case:
- H. S. Teoh (8/26) Dec 24 2013 [...]
- H. S. Teoh (6/31) Dec 24 2013 [...]
- Craig Dillabaugh (4/27) Dec 24 2013 Doesn't think work, or am I missing something?
- Craig Dillabaugh (5/11) Dec 24 2013 clip
- H. S. Teoh (5/18) Dec 24 2013 You mean, a tpyo? :-P
- Craig Dillabaugh (2/21) Dec 24 2013 Exactly!
- Andrei Alexandrescu (3/24) Dec 24 2013 Use a spellchequer.
- Andrei Alexandrescu (4/29) Dec 24 2013 I doubt it's anything as simple as that. The magnitudes of up, low, and
- H. S. Teoh (8/23) Dec 24 2013 [...]
- Andrei Alexandrescu (25/45) Dec 24 2013 No, again, I think nothing like that would work. It's hopelessly naive
- H. S. Teoh (10/59) Dec 24 2013 Aren't you accumulating roundoff errors here? Since + may introduce an
- Andrei Alexandrescu (4/38) Dec 24 2013 Ideally one addition is all needed for popBack.
- H. S. Teoh (26/68) Dec 24 2013 [...]
- Andrei Alexandrescu (45/61) Dec 24 2013 It's Christmas, let's be nice to one another :o). The only problem here
- Joseph Rushton Wakeling (9/26) Dec 24 2013 Complication: as it stands, iota is defined as an open interval; its val...
- H. S. Teoh (8/39) Dec 24 2013 This code is wrong for iota(1.0, 9.5), because .back must be of the form
- Jakob Ovrum (3/11) Dec 28 2013 It is a simplified example. It has no pretence of handling
- Joseph Rushton Wakeling (3/7) Dec 24 2013 I don't see the reason why there needs to be a start == end condition --...
- Andrei Alexandrescu (3/4) Dec 24 2013 This is better start >= end if ordering comparisons are supported.
- Francesco Cattoglio (11/13) Dec 24 2013 I would like to add that I want to compute back because the
- Jakob Ovrum (8/10) Dec 28 2013 If it can't be defined reasonably for a custom step[1], then
- Joseph Rushton Wakeling (2/4) Dec 28 2013 Are you sure that's going to work if the iota covers a leap year? :-)
- Francesco Cattoglio (3/9) Dec 28 2013 And that's exactly the reason I choose 2012 as an example :D
- Joseph Rushton Wakeling (6/7) Dec 28 2013 It's going to get fun if we have to start taking into account leap secon...
- Jakob Ovrum (4/6) Dec 28 2013 How would it fail? std.datetime does a good job with leap years
- Joseph Rushton Wakeling (4/5) Dec 28 2013 Try the attached code. The largest value of DateTime(2012, 1, 1) + dur!...
- Jakob Ovrum (4/9) Dec 28 2013 OK, so this has nothing to do with leap years, but that 5.days is
- Joseph Rushton Wakeling (4/5) Dec 28 2013 Oh, I see -- you're assuming that iota has to be defined with start, end...
- Jakob Ovrum (5/7) Dec 28 2013 Yes, I can totally see that. I'm not really invested either way,
- Francesco Cattoglio (10/16) Dec 28 2013 Yes it does, the catch is:
- Jakob Ovrum (5/8) Dec 28 2013 Alright, so require division for bidirectionality when given a
- Francesco Cattoglio (7/10) Dec 28 2013 Ok, now I finally get your point. It goes something along the
- Jakob Ovrum (8/19) Dec 28 2013 As long as `start < end` is true in the beginning, that's a
- monarch_dodra (3/12) Dec 24 2013 Actually, if the range is infinite, then you can also have RA
- Joseph Rushton Wakeling (9/14) Dec 24 2013 Example case:
- Andrei Alexandrescu (22/79) Dec 23 2013 I think it makes a lot of sense to relax that. Different types have
- bearophile (22/26) Dec 25 2013 Probably directly addressed by issue 10762:
- Francesco Cattoglio (11/20) Dec 25 2013 Wow! That's a lot of stuff needing work. Now I understand why
- H. S. Teoh (28/32) Dec 27 2013 [...]
- Iain Buclaw (3/32) Dec 29 2013 For GDC, 'appears to work like' gets turned into 'it calls' fmod(x, y) i...
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
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
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
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
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: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.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
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
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 :PNo, 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
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
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, bearophileNice 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
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
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: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.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
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
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: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).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.
Dec 24 2013
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
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: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.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
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
On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:On 24/12/13 13:58, monarch_dodra 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? AndreiI 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
On Tue, Dec 24, 2013 at 09:10:53AM -0800, Andrei Alexandrescu wrote:On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:[...] 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? -- YHLOn 24/12/13 13:58, monarch_dodra 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?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
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:[...] Maybe (up - fmod((up-low), step)) might be better? I'm not 100% sure. T -- VI = Visual IrritationOn 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:[...] 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.On 24/12/13 13:58, monarch_dodra 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?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
On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepOn 24/12/13 13:58, monarch_dodra 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? AndreiI 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
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:clipOn 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepI meant "Doesn't this work". Why can't I ever make a post without a typo!
Dec 24 2013
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:You mean, a tpyo? :-P T -- No! I'm not in denial!On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:clipOn 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepI meant "Doesn't this work". Why can't I ever make a post without a typo!
Dec 24 2013
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:Exactly!On Tuesday, 24 December 2013 at 18:56:02 UTC, Craig Dillabaugh wrote:You mean, a tpyo? :-P TOn Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:clipOn 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepI meant "Doesn't this work". Why can't I ever make a post without a typo!
Dec 24 2013
On 12/24/13 11:17 AM, Craig Dillabaugh wrote:On Tuesday, 24 December 2013 at 19:08:40 UTC, H. S. Teoh wrote:Use a spellchequer. AndreiOn Tue, Dec 24, 2013 at 06:57:50PM +0000, Craig Dillabaugh wrote:Exactly!On Tuesday, 24 December 2013 at 18:56:02 UTC, Craig Dillabaugh wrote:You mean, a tpyo? :-P TOn Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei >Alexandrescu wrote:clipOn 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepI meant "Doesn't this work". Why can't I ever make a post without a typo!
Dec 24 2013
On 12/24/13 10:56 AM, Craig Dillabaugh wrote:On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account. AndreiOn 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:Doesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepOn 24/12/13 13:58, monarch_dodra 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? AndreiI 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
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:[...] 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. -- JMI doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.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? AndreiDoesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
Dec 24 2013
On 12/24/13 11:59 AM, H. S. Teoh wrote:On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote: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: 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); } AndreiOn 12/24/13 10:56 AM, Craig Dillabaugh wrote:[.[..]On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.)I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.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? AndreiDoesn't think work, or am I missing something? low + floor( (up-low)/step ) * step
Dec 24 2013
On Tue, Dec 24, 2013 at 12:57:02PM -0800, Andrei Alexandrescu wrote:On 12/24/13 11:59 AM, H. S. Teoh wrote:Then what should be returned in that case?On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote: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.On 12/24/13 10:56 AM, Craig Dillabaugh wrote:[...]On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.)I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.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? AndreiDoesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepTry this to verify approaches: 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
On 12/24/13 1:09 PM, H. S. Teoh wrote:On Tue, Dec 24, 2013 at 12:57:02PM -0800, Andrei Alexandrescu wrote:The same as an iota with step zero.On 12/24/13 11:59 AM, H. S. Teoh wrote:Then what should be returned in that case?On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote: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.On 12/24/13 10:56 AM, Craig Dillabaugh wrote:[...]On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.)I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.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? AndreiDoesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepIdeally one addition is all needed for popBack. Andreiauto next = low + step;Aren't you accumulating roundoff errors here?
Dec 24 2013
On Tue, Dec 24, 2013 at 01:18:34PM -0800, Andrei Alexandrescu wrote:On 12/24/13 1:09 PM, H. S. Teoh wrote:[...] 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 EllisOn Tue, Dec 24, 2013 at 12:57:02PM -0800, Andrei Alexandrescu wrote:The same as an iota with step zero.On 12/24/13 11:59 AM, H. S. Teoh wrote:Then what should be returned in that case?On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote: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.On 12/24/13 10:56 AM, Craig Dillabaugh wrote:[...]On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:[...] What about low + fmod(up-low, step)*step? Is that better? (Assuming that fmod would take relative magnitudes into account, of course.)I doubt it's anything as simple as that. The magnitudes of up, low, and step must be taken into account.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? AndreiDoesn't think work, or am I missing something? low + floor( (up-low)/step ) * stepIdeally one addition is all needed for popBack.auto next = low + step;Aren't you accumulating roundoff errors here?
Dec 24 2013
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
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
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: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...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
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
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
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
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
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
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
On Saturday, 28 December 2013 at 12:16:32 UTC, Joseph Rushton Wakeling wrote:On 28/12/13 09:06, Jakob Ovrum wrote:And that's exactly the reason I choose 2012 as an example :D[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
On 28/12/13 14:16, Francesco Cattoglio wrote:And that's exactly the reason I choose 2012 as an example :DIt'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
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
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
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
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
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
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: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.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
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
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
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: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.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
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:Actually, if the range is infinite, then you can also have RA without bidirectionality.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.
Dec 24 2013
On 24/12/13 11:38, Francesco Cattoglio wrote: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.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
Dec 24 2013
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
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
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 tooWow! 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 thisBye, bearophileI 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
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:[...][...] 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.(A less important enhancement is issue 11252).On the other hand, I have honestly no idea whatsoever about how to implement this
Dec 27 2013
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:For GDC, 'appears to work like' gets turned into 'it calls' fmod(x, y) in D. :)On Wednesday, 25 December 2013 at 10:58:53 UTC, bearophile wrote:[...][...] 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); } }(A less important enhancement is issue 11252).On the other hand, I have honestly no idea whatsoever about how to implement this
Dec 29 2013