proposal: spec: allow range over arbitrary types

[ibnesayeed]

Slice is a powerful and commonly used data structure in Go to organize multiple items in a sequence, but there are cases where List is a better choice. One such case could be where the number of items is large and arbitrary items are inserted one by one while maintaining certain sort order. Insertion or deletion at arbitrary places in a Slice would cause relocation of the trailing items.

For this reason if one chooses to use List over Slice, it comes with a cost of not being able to use Range iterator syntax. Consequently, the List is not supported by the template iterator system ({{range pipeline}}) either.

Hence, I am proposing the addition of Range iterator support for List data structure.

[ianlancetaylor]

This is a little vague. Are you suggesting a language change or a change to the text/template package? Can you describe the change more precisely? You mention the List data structure, but there is no such data structure in Go.

[ibnesayeed]

You mention the List data structure, but there is no such data structure in Go.

I am referring to the built-in implementation of the doubly linked list package. I think the template system will automatically start supporting it (unless there is hardcoded restriction to certain data structures) if the required iterator functionality is added to the List implementation.

I am not much aware of the Go internals as I am new to this language, but I am thinking along the lines of how Sorting functionality is added to any arbitrary struct by attaching the necessary interface to it.

[adg]

It's rare that people use container/list. Most programmers opt for just
using slices instead.
I think the combination of container/list and templates is an order of
magnitude rarer.
It doesn't seem like something worth creating a special-case for.

On 23 October 2015 at 11:59, Sawood Alam notifications@github.com wrote:

You mention the List data structure, but there is no such data structure
in Go.

I am referring to the built-in implementation of the doubly linked list
https://golang.org/pkg/container/list/ package. I think the template
system will automatically start supporting it (unless there is hardcoded
restriction to certain data structures) if the required iterator
functionality is added to the List implementation.

I am not much aware of the Go internals as I am new to this language, but
I am thinking along the lines of how Sorting functionality is added to any
arbitrary struct by attaching the necessary interface to it.

—
Reply to this email directly or view it on GitHub
#13027 (comment).

[ibnesayeed]

Looking at the specs, I think it will require changes in the language, not just in the package implementation. Here is what the RangeClause grammar says:

The expression on the right in the "range" clause is called the range expression, which may be an array, pointer to an array, slice, string, map, or channel permitting receive operations.

However, this explicit list of white-listed data types/structures is limiting. In my opinion, the range clause should have certain set of conditions, that, if fulfilled by any data structure, should be supported as an iterator. Those conditions could be something like this:

• must have a definite start and an end
• must provide a guaranteed traversal path from the start to the end
• must provide a well known way of transitioning from one node to the next

[griesemer]

Depending on how text templates decide how to iterate (i.e., whether they look at the actual type and/or whether there's an "iterator" channel present), this may require as little as adding a method returning a channel yielding the list elements to container/list.

If that's the only required change, I might not mind.

But I suspect it might be more involved. And in that case I'm with @adg: I don't think this is warranted. The container/list is in the std/lib mostly for historic reasons, and is almost always overkill and slower than any other solution. Adding a channel on top of it to simplify iterations will only make things worse.

@ibnesayeed your latest suggestions at extending the range clause is out of the question for Go 1.0.

[ibnesayeed]

It's rare that people use container/list. Most programmers opt for just using slices instead.

There are cases where linked list is a better and more efficient choice than slices. Calling it rare is more like introducing something half-baked in the language core packages and then removing it later saying it was not well received. If my use case is not very specific where I must use certain data type, I would probably switch to something less efficient but more convenient.

I think the combination of container/list and templates is an order of magnitude rarer.

It is not about supporting the template, it is about supporting the range iterator, template will follow that automatically (I guess).

It doesn't seem like something worth creating a special-case for.

It's more along the lines of generalization of the iterator, not specialization.

[adg]

Calling it rare is more like introducing something half-baked in the language core packages and then removing it later saying it was not well received

We would remove container/list if we could.

[griesemer]

@ibnesayeed Again, as long as a data type supports a channel, you can iterate over it. But there is no chance that we are going to change how range works in any fundamental way.

[ibnesayeed]

as long as a data type supports a channel, you can iterate over it.

Thanks @griesemer for this tip. I am not a big fan of adding unnecessary shims, especially, when I am fighting for performance and memory footprint over the elegance of the code, but I will keep this in the back of my head for places where this trick might actually be useful.

@ibnesayeed your latest suggestions at extending the range clause is out of the question for Go 1.0.

I think you mean 1.x, right?

But there is no chance that we are going to change how range works in any fundamental way.

I think calling it a fundamental change depends on how we see it. Looking at the specs, I don't immediately see any grammar clause that will require changes. I do understand that not all the semantics can be described in the EBNF and requires additional plain text to complement it. However, rephrasing the complementary text to extend it and make it more inclusive should not be a problem. The proposal document does talk about compatibility as follows:

Programs written for Go version 1.x must continue to compile and work with future versions of Go 1.

Which I think will remain valid after this proposed change.

[ibnesayeed]

We would remove container/list if we could.

I think I am not much concerned about what is available as the core package and what requires a third party package. The point I was trying to make is, sometimes, how much something is used depends on how well that is supported. Take an example of a language that has excellent support of arrays, but very poor and basic support of dictionaries. Programmers of that language will often prefer using combinations of array tricks to achieve more than what they can by the native implementation of the dictionary. On that ground, saying that dictionary is a rarely used data structure is true, but not true.

Almost all data structure books talk about arrays and linked lists together on the same fundamental data structure level. Both have their advantages and disadvantages. However, I do agree that array is a more commonly used data structure in real life applications than linked list, but if it is supported as first class data structure by the language and gets the same degree of love, then the usage will not be rare.

I think the point of this proposal is to make the range clause more generic that iterates over any collection that satisfies certain conditions. List being just one example of such a collection that can leverage this extension.

[adg]

Sorry for being brief. This has come up before. I'll expand on some of my thoughts about this:

• The obvious way to implement something like this is to recognize an Iterable interface (or similar), and allow types to implement that interface to be used with range.
• In Go the only way to execute code is with a function call. There is no operator overloading, no subtype inheritance, no generators (what you're asking for), etc. This means to read Go code you just follow the function calls; you needn't look at a piece of code and wonder whether it is executing some code somewhere else. If there's a function call then you can follow execution into a function. If there isn't, you can keep reading down the page. This property improves readability, and one of Go's key design objectives is readability.
• The language doesn't treat any interfaces specially. The only interface recognized by the spec is error, but that exists as a built in convention and nothing more. The introduction of Iterable would establish a new precedent. We are now 6 major releases into Go 1, and it is unlikely we will make such a dramatic change at this point.

[ibnesayeed]

Thanks @adg for the insights. I appreciate your time and agree that from the implementation perspective it might be a big change, despite being backward compatible. That said, is it something that can be forgotten about as if it was never considered or such changes are pushed to the distant 2.0 release that is not on the radar yet?

[rsc]

This would be for Go 2. Marking with label Go2 and Proposal so we can find it, but also declining and closing the issue, because we're nowhere near thinking about Go 2 yet.