Sets

[Robert Engels]

The github set issue is impossible to follow without using github.

Please simply define the interfaces. The implementations will follow. You can have simple iterators, indexed iterators, map (key/value) iterators, errorable iterators, closable iterators.

You can define how to provide/adapt for/range support to these interfaces later. It is confusing the discussion. Since range is a built in - once the interfaces are defined it is straightforward to discuss for/range support.

[Ian Davis]

Do you have a link to your proposed interface?

[robert engels]

I do not. A lot depends on if you want to use optional methods which is difficult in Go, but many have given plenty of starting ideas.

type Collection interface {
Contains(e E) bool // may be slow, requiring a scan
Iterator() ElementIterator[E]
}
type Set interface { // simply a marker that the collection has unique elements
Collection
}
type MutableSet interface {
Set
Add(e E) bool
Remove(e E) bool
}
type ElementIterator interface {
Next() (E,bool)
Error() error
Close() error
}

Error() and Close() are simply no-ops for memory containers (usually).

type Map interface {
ContainsKey(k K) bool
Get(k K) (V,bool)
Iterator() KeyValueIterator[K,V]
}
type MutableMap interface {
Put(k K,v V) bool
Remove(k K) bool
}

type KeyValueIterator interface {
Next() (K,V,bool)
Error() error
Close() error
}

type List interface {
Get(int) (E,bool)
Iterator() ListIterator[int,E]
}

type ListIterator interface {
Next() (int,E,bool)
Error() error
Close() error
}

Now of course, you could add methods to List like

SubList(start,end) List[E]

and so on. Depends on how you much want to bite off. Most other languages that have collectons in the stdlib are a good reference. Not sure above making MutableXXXX, vs adding an error to mutating operations (or panic) if it is not supported.

Obviously the above prohibits a map container from implementing the ElementIterator and the other - but you could change the signatures to avoid that but it seems easier to add methods to the interface, for example:

type Map interface {
KeySet() Set[K]
ValueSet() Set[V]
AsCollection() Collection[KeyValue[K,V]]
}

many of these types of methods can be implemented as standard utility methods, e.g. map.KeySet(somemap).

Now comes the fun part, since range is a built-in, simply have it determine the valid method based on the return value count, and ensure the collection types matches

k,v := range somemap

or

v := range somemap.ValueSet()

or

i,v := range somelist

e := range someset

It would be a compile error to use

k := range somemap

it decomposes so that range simply works on ElementIterator, KeyValueIterator, and ListIterator.

It is trivial to create an instance of the above given a builtin slice, or a map.

The close/error can be condensed to close, if close is defined to always return the last error encountered as would have been returned by Error() (or a wrapped error). Iterators that needs it would add Close() to the finalizers for safety. You still have the same problem with the “real” proposal - how do you get the itr reference to Error()/Close().

So maybe for Go, it always has to be:

itr := somecollection.Iterator()

for x := range itr {
..
}
if err = itr.Close() {
}

I don’t think range adds much in this case over a for loop.

Anyway, not fully fleshed out but I think it would work. range already has lots of special case handling - adding support for the standard library collections seems natural.

All of the other operations, like set.Intersect(s1,s2) can be concrete in the package.

I think discussing the interfaces and names would be a more productive discussion. Once these are decided I think it is very easy to discuss implementations. I think a standardized collections package is more important than range support.

> --
> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/b18539f6-dce0-4a63-950f-994c3b4cf4f9%40www.fastmail.com.