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.

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.

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.

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)];
}

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).

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);
}
---

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?

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.

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.

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.