Reverse range in Go

[Accipiter Nisus]

The subject has been mentioned before, but I never seen the reason why this functionality doesn't exist.

I don't see any direct negative side effect of it.

For array and slice:

Just like range makes looping a bit less verbose and tidier, a range reverse would have the same nice effect

For map:

Not allowed since maps have no set order

For string:

It would in some cases make code less cluttered and easier to understand. Compare finding the index of the last instance of a rune (without strings):

s := "ärkeängel"

// Without range reverse

sc := s // If we want to keep the original string

for len(sc) > 0 {

r, size := utf8.DecodeLastRuneInString(sc)

if r == 'ä' {

fmt.Println(len(sc)-size)

break

}

sc = sc[:len(sc)-size]

}

// With range reverse

for i, r := range s reverse {

if r == 'ä' {

fmt.Println(i)

break

}

}

[Matt Kane's Brain]

On Mon, Nov 26, 2012 at 7:24 AM, Accipiter Nisus <acci...@gmail.com> wrote:

// Without range reverse

sc := s // If we want to keep the original string

for len(sc) > 0 {

r, size := utf8.DecodeLastRuneInString(sc)

if r == 'ä' {

fmt.Println(len(sc)-size)

break

}

sc = sc[:len(sc)-size]

}

It doesn't need to be this complicated. You can directly convert a string to a rune slice without a range clause:

sr := []rune(s)

for i := len(sr) - 1; i >= 0; i-- {

  if sr[i] == 'ä' {

  fmt.Println(i)

  break

  }

}

    

--
matt kane's brain
http://hydrogenproject.com

[Accipiter Nisus]

True that you can turn it all into a []rune slice, but if you have a very large string you want to avoid doing that.

Also, our two functions will return different values.

My function will return the byte index of 'ä' within the UTF-8 sequence (5), while your function returns the 'ä' character index (4).

[Kevin Gillette]

Remember that range loops can take arbitrarily long expressions, like:

for x := range Some.Long.Expression["returning"]("an appropriate iterable") {}

Due to this, if the keyword "reverse" were introduced, it would be much less staggering to many if it were put before, rather than after, the expression, such as:

for x := reverse range s {}

or

for x := range reverse s {}

That said, as long as it's proposed that a keyword be added for which we currently have no other purpose, I'd suggest "revrange" would be equally appropriate, and syntactically simpler.

Obviously, channels couldn't be reversed either.

[Jan Mercl]

On Tue, Nov 27, 2012 at 2:44 PM, <gordon...@gmail.com> wrote:
> My vote is for the "egnar" keyword.

Mine goes to "citemhtiraxedniesu".

-j

[Kevin Gillette]

The string handling convenience of range loops would be the counter-point.

[roger peppe]

> Compare finding the index of the last instance of a rune (without strings):

um, strings.LastIndex ?

for myself, that particular functionality is about the
only thing i ever need to iterate through a string in reverse
for. (iterating in reverse through a slice is trivial; iterating
in reverse through maps or channels makes no sense)

the fact that it's so infrequently required makes me think
that the functionality probably doesn't deserve a place
in the core language.

FWIW you can use strings.LastIndexFunc as a reverse-range
iterator, although it doesn't tell you the index at each code point.

> --
>
>

[Rui Maciel]

Adding extra keywords to a programming language just to hack up a
solution to a corner case is always bad. Always. No exception.

I believe a far better idea would be to simply support iterators, or
even slices whose index would be mapped as ri = len(s) - i. One
possible way to define this sort of slice would be to call make() with a
negative value for the length.


Rui Maciel

[Kevin Gillette]

On Tuesday, November 27, 2012 9:05:25 AM UTC-7, Rui Maciel wrote:

Adding extra keywords to a programming language just to hack up a
solution to a corner case is always bad.  Always. No exception.

I believe a far better idea would be to simply support iterators, or
even slices whose index would be mapped as ri = len(s) - i.  One
possible way to define this sort of slice would be to call make() with a
negative value for the length.

I agree with the "don't add a keyword" keyword part, not with the iterator part. We already have channels which _can_ count as iterators. While it's not, conceptually, an 'exact fit', it's arguably better than breaching the clear boundary between the core language and the libraries by adding the first core-recognized interface. If you argue that an iterator interface is better because function calls are currently cheaper than channel ops, then the answer is to use channels and work to make channels cheaper for certain iterator-like usages. This can be done through escape analysis -- if the channel is unbuffered and doesn't escape the two goroutines involved in iteration (and any select statements only operate on channels shared between those two goroutines), then special-case it and turn channel ops into jmp instructions.

Modifying slices has been discussed, such as to support a "step" whose absolute value isn't 1, and those add a great deal of complexity to the slice structure, or make slices "non-cheap" in various ways. If it's only a matter of allowing a reversed slice or string, that wouldn't complicate the underlying structures, since it could be encoded with a negative length, as you say. Using make to "create" a reversed slice seems moot, since a truly reversed slice would have all index operations, not just range iteration, reversed, thus it isn't really reversed if you make a zeroe'd slice. Extended/augmented slice syntax doesn't really fit too well (`s[-:]` would be cryptic, and the python-style syntax of `s[::-1]` would give people the wrong idea unless we actually want to support an arbitrary 'step'), so a builtin, like 'reverse' or 'rev' would be cleaner, I believe.  The only problem with reversed strings is that they aren't cleanly usable in reverse when they contain non-7bit-ascii data -- reverse iteration makes sense, but reversed index access does not. That thought alone makes me think this is all much more trouble than it's worth.

[Accipiter Nisus]

I would agree if I thought it was just a corner case.

Reverse iteration is common enough, and since the Go language is meant to have a clean feel, the gain of adding a keyword is worth it

for i:=len(s)-1; i >= 0; i-- {}

to:

for i := revrange s {}

It would

* add make reverse iterations more clean

* make range iteration and reverse range iteration get the same style

* help avoid stupid bugs like typing i>0 instead of i>=0

* add functionality when reverse iterating strings

* be easy to implement with current slices/strings/arrays without having to alter the internal structures of a slice (like your iterator suggestion)

Cost:

* A new self-explaining keyword

I'd happily pay that price :)

[Miki Tebeka]

range works also on maps and channels. revrange won't since there's no definition of reverse of map and you need to wait for a channel to be closed to do a reverse. This means they are not that close.

[Accipiter Nisus]

On Wednesday, 28 November 2012 16:08:24 UTC+1, Miki Tebeka wrote:

range works also on maps and channels. revrange won't since there's no definition of reverse of map and you need to wait for a channel to be closed to do a reverse. This means they are not that close.

Using revrange on a channel or map should indeed result in a compiler error.

But, if that is an argument against reverse range, then the same could be said about other builtin's such as cap that doesn't work on strings, or append that only works on slices.

The reason why cap doesn't work on strings is because it doesn't apply to the structure of that specific type.

Reverse range won't apply to all types that range applies to, but that doesn't mean it shouldn't exist.

[André Moraes]

Reverse range string in less time than what i spent reading this topic
(and without language changes).

package main

import (
"fmt"
"unicode/utf8"
)

type Rev struct {
Val string
Cur rune
}

func (r *Rev) Next() bool {
var sz int
r.Cur, sz = utf8.DecodeLastRuneInString(r.Val)
if r.Cur != utf8.RuneError {
r.Val = r.Val[0:len(r.Val)-sz]
}
return r.Cur != utf8.RuneError
}

func main() {

r := &Rev{Val: "my string"}
for ; r.Next(); {
fmt.Printf("%v\n", string(r.Cur))
}
}


Could be improved of course.
--
André Moraes
http://amoraes.info

[Rui Maciel]

On 11/28/2012 03:36 PM, Andr� Moraes wrote:
> Reverse range string in less time than what i spent reading this topic
> (and without language changes).

You've declared a pointer, along with an iterator function that
increments the pointer. That is not a reverse range. It's not even the
first alternative to a reverse range that doesn't require changing the
language which was posted to this discussion.

Maybe you should had spent some time reading the topic after all.


Rui Maciel

[Ian Lance Taylor]

On Wed, Nov 28, 2012 at 7:20 AM, Accipiter Nisus <acci...@gmail.com> wrote:
>
> Using revrange on a channel or map should indeed result in a compiler error.
> But, if that is an argument against reverse range, then the same could be
> said about other builtin's such as cap that doesn't work on strings, or
> append that only works on slices.

Since you can't do a reverse range on a channel or map, that leaves on
slices, arrays, and strings. Doing a reverse iteration over a slice
or array is trivial, and I doubt it is common enough that it deserves
a special syntax. That leaves only reverse iteration over strings.
While a reverse range on a string is not trivial, I doubt that it is
common. It can, of course, be implemented using functions that are
just as efficient as any possible runtime code.

So I don't see a compelling argument for adding new syntax for this.
It doesn't add very much. In my opinion, certainly not enough to add
a new keyword to the language.

Ian

[Steven Johnson]

On Wed, Nov 28, 2012 at 8:14 AM, Ian Lance Taylor <ia...@google.com> wrote:

Doing a reverse iteration over a slice or array is trivial

Doesn't using "range" allow the compiler to avoid out-of-bounds-access checks on each loop iteration, thus potentially making the loop more efficient? 

If so, it would be nice if reverse-iteration could take advantage of a similar optimization.

(If not... um, why not?)

[André Moraes]

On Wed, Nov 28, 2012 at 11:41 PM, Steven Johnson <s...@google.com> wrote:
>
>
> On Wed, Nov 28, 2012 at 8:14 AM, Ian Lance Taylor <ia...@google.com> wrote:
>>
>> Doing a reverse iteration over a slice or array is trivial
>
>
> Doesn't using "range" allow the compiler to avoid out-of-bounds-access
> checks on each loop iteration, thus potentially making the loop more
> efficient?

for i, v := range array {
if v > array[i+1] {
// do something if the array is out of order
}
}

The loop above require the bound check, but in cases where the code
inside the loop never touch the slice object, than those check's could
be removed.

[André Moraes]

> You've declared a pointer, along with an iterator function that increments
> the pointer. That is not a reverse range. It's not even the first
> alternative to a reverse range that doesn't require changing the language
> which was posted to this discussion.

Why not?

reverse-range in map/channels don't make sense
reverse-range in slices can be done with ordinary loop (i-- instead of i++)
the only problem left was reverse range in a string iterating over
runes instead of bytes,
my code does exactly that, solves the problem (coulde be optimized I
agree) without changing the language.

My code uses just a few bytes than a ordinary string (namely the Cur
field which uses 4 bytes), the string is just a slice, so zero data is
copied. And structs in Go don't have hidden costs.

The only drawback is making a function call in every loop, but those
tend to be pretty fast anyway.