Ranges with strides

[apblack]

I've long found it annoying that, while we have a nice notation for ascending ranges,

1 .. 4

we don't have one for descending ranges like [4, 3, 2, 1]. No, we can't allow 4..1, because that's an empty range. (1..4).reversed works, but is long-winded. range.from 4 downTo 1 is the primitive constructor, and it's even longer-winded.

A possible soution is to devise a general notation for "strided ranges" (or should it be "stridden" ranges?) For example

1 .. 4 .. 1    => same as 1 .. 4, because 1 is the default stride
1 .. 10 .. 2  => [1, 3, 5, 7, 9]: a stride of 2, starting at 1 and continuing until the next element would exceed the second bound
4 .. 1 .. -1  =>  [4, 3, 2, 1]: a stride of -1, starting at 4 and continuing until the next element would be less than the second bound

This could be implemented pretty easily by defining the .. operator on ranges.

[KimBruce]

Languages like Haskell have already dealt with this issue. Haskell arithmetic sequences can be written as [1 .. 30] or [1,4 .. 30]. The first is similar to what we now support, while the second gives the implicit gap (4-1 or 3). We could do the same thing, but without the square brackets.

I don't like your proposed notation as the two sets of ".." mean different things -- the first for a range and the second for the gap. I suspect it is illegal with our naming rules, but 1 .. 30 by 3 would be more attractive to me. Alternatively we could have .. give the range and have a "by" method that filters the range. I.e., 1..30.by 3 would indicate the range where you grab the 1st, 4th, etc. elements.

At any rate, I'm not a big fan of your proposal -- and I wouldn't even mind writing "rangeFrom 1 to 30 by 3" when you need the stride different from 1.

[apblack]

I presume that you are not opposed to the idea of creating strided range objects, and that what we are discussing here is syntax. I am also aware that other languages have addressed this problem; Fortress, for example, uses 1:10:2 to mean [1, 3, 5, 7, 9], and was the inspiration for my proposal. We can't use :, though, because it's not an operator in Grace, and :: is taken.

We could indeed do what you are proposing and invent some new syntax. Haskell's range notation is an example of that: [a, b, .. c] is actually just a shorthand for enumFromThenTo a b c. Since in Grace [ ... ] is already special syntax, we could give comma and dot dot special meaning within the brackets, and copy what Haskell does. (I don't think that we could use .. or ..., though, because they already have meaning in or as expressions.)

In this proposal, I am trying to avoid changing the language and do this in a library with Grace operators, which is what we have done so far with .. . I secretly agree with you that using .. for both the operator symbols is not great; the problem is that our syntax forbids adjacent operators unless they are the same. So, for example, 1..10#2 would not be legal: one would have to write (1..10)#2 or 1..(10#2), and the parenthesis are ugly. In contrast, my suggestions 1..10..2 and 10 .. 1 .. -1 are both legal, and could be implemented simply by defining .. on ranges. (Note, though, that the space between .. and - is required, otherwise it would be a request of the ..- operator.)

I'm proposing that we look at syntaxes that are already legal before we resort to extending the language.

Of your suggestions, 1 .. 30 by 3 is not legal. 1 .. 30.by 3 is legal, and is parsed as 1 .. (30.by 3). So we could make that work at the cost of double dispatching every range construction to distinguish between the argument to .. being a number and a by object. Unfortunately, my motivating example is not legal: 30 .. 1.by -1 treats the - as a binary operator and complains because the two binary operators .. and - differ. One would have to write 30 .. 1.by(-1). Once we are doing that, it would probably be better to write (30 .. 1).by(-1), and at least get a natural order of operations.

A different approach would be to use another operator for downward ranges; something like 10 .-. 1 for "10 down to 1". However, the only operator that is mnemonic to me is ↓, giving 10↓1. That looks fine, but can't be easily typed.

[apblack]

Yet another possibility is to define to(_) and to(_)by(_) (and even downTo(_)) as methods on numbers:

1.to 10 by 2
10.to 1 by (-1)
10.downTo 1

and so on. This may be the simplest notationally, but encumbers the Number protocol with more conversion methods.

[kjx]

I'd go with .. on ranges. The fun question is: .. on collections.

[apblack]

The fun question is: '. on collections.

I don't understand the "fun question".

I've implemented .downTo on numbers in minigrace in commit afc5692. This seems useful, regardless of what eventually happens for strided ranges.

[kjx]

I don't understand the "fun question".

supposed to be .. on collections. If (1 .. 11 .. 2) yields 1 3 5 7 9 11 then what about list(1,2,3,4,5,6,7,8,9,10,11) .. 2

[apblack]

Initially, I thought that .. should be defined only on ranges. But it does make perfect sense on any enumerable collection: it means "stride". ..1 means "every element", ..2 means "every other element", ..3 means "every third element", and so on. So, for your example, list [1,2,3,4,5,6,7,8,9,10,11] .. 2 would mean list [1, 3, 5, 7, 9, 11]. The important point is that a stride of n means increase the index by n, not the element value. Hence, list [2, 3, 5, 7, 11, 13, 17]..3 would mean list[2,7,17].

[kjx]

well I kind of think it makes sense. Not clear how "a" .. "z" .. 0.5 or "z" .. "a" .. -1` works.

Consider seq("z","y","x","w","v",) .. 1 comparing "z" .. "a" .. 1 and "a" .. "z" .. -1

[apblack]

Non-integer strides clearly make no sense. Neither do negative strides, with this interpretation — what would a stride of -2, meaning "every negative other element" mean?

However, if we assume the meaning of "a".."z" to be known, then "a".."z"..2 is clear: every other element of the sequence "a".."z"

[KimBruce]

While I agree with Andrew on positive integer strides, I continue to hate the notation!

[apblack]

If .. n on sequences (including ranges) means stride, that is, every nth element, then negative strides make no sense. So the original motivating example — 4.downTo 1 is still in search of a syntax.

One option is to make a negative stride mean "first reverse the target, and then apply the negation of the stride". (I think that this is equivalent to: start striding from the upper bound, and add the (negative) stride to the index at each step.) So, 1 .. 4 .. -1 would mean:

1 .. 4 .. -1
(range.from 1 to 4) .. -1
(range.from 4 downTo 1) .. 1 
(range.from 4 downTo 1)

I also don't love the double use of .. to mean range on numbers, but stride on indexed collections. Our options seem to be

1. to change the language to allow sequences of dissimilar operators (which probably means either ternary operators, or strict left-to-right precedence), or
2. to adopt some mixed-operator-named-method combination, such as 1..4.by(-1), which is horrible both syntactically and semantically, or
3. add special-purpose syntax for this particular purpose, as @KimBruce suggested above, or
4. think of something else.

As a side effect of thinking about this, I realize that 4..1 and 7..0 are ==: they are both empty ranges. They are behaviorally identical, except for one thing: their asString methods produce different results. This makes me think that their asString methods should both answer "[]", and their asDebugString methods should do what asString does now. ((4..1) == [] is true, so giving them the same printString makes sense.)

print((4 .. 1) == (7..0))     // => true
print(4..1)                   // => range.from(4)to(1)
print(7..0)                   // => range.from(7)to(0)

[kjx]

I don't see the problem of a range vs a collection - I mean, isn't a range 1..4 essentially the collection [1, 2, 3, 4]? (I'd write seq(1,2,3,4) of course but that's something else to quibble about.

[apblack]

I don't see the problem of a range vs a collection

Neither do I. Ranges are just an implementation of Sequence.