Question on the generics proposal and arrays

[Markus Heukelom]

It appears to me the current proposal does not allow you to write a function that sorts an array of any size:

func SortArray[T comparable](array [??]T, less func(a, b T) bool) [??]T {}

Is it correct that this is not possible? Or is this expressed differently?

To clarify, I am seeking for something like:

func SortArray[T comparable, int n](array [n]T, less func(a, b T) bool) [n]T {} 

Here's two other examples that come to mind:

type Number {types ...}

func DotProduct[T Number, int n](a, b [n]T) T {} // n can be any integer

func MultMatVec[T Number, rows, cols int](m [rows][cols]T, v [cols]T) [rows]T {}

Thanks, Markus

[Viktor Kojouharov]

This would require something similar to rust's const generics. IIRC, that's not on the table with the initial draft

[Ian Lance Taylor]

On Tue, Oct 6, 2020 at 6:32 AM Markus Heukelom <markus....@gain.pro> wrote:
>
> It appears to me the current proposal does not allow you to write a function that sorts an array of any size:
>
> func SortArray[T comparable](array [??]T, less func(a, b T) bool) [??]T {}
>
> Is it correct that this is not possible? Or is this expressed differently?
>
> To clarify, I am seeking for something like:
>
> func SortArray[T comparable, int n](array [n]T, less func(a, b T) bool) [n]T {}

You are correct that the current design draft does not provide any
mechanism for writing code that is generic across the dimension of an
array. This is mentioned in the list at
https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#omissions.
I don't think it would be hard to add later if it seems useful.

That said, I don't think your suggested SortArray function would be a
good API. In Go arrays are passed by value, so this would copy the
entire array into the function, sort it, and then copy the entire
array out. It is trivial to turn an array into a slice, by writing
a[:], so it would be more natural in Go to write Sort(a[:], less),
which would let the caller decide whether to make a copy or not.

> Here's two other examples that come to mind:
>
> type Number {types ...}
> func DotProduct[T Number, int n](a, b [n]T) T {} // n can be any integer
> func MultMatVec[T Number, rows, cols int](m [rows][cols]T, v [cols]T) [rows]T {}

Agreed.

Ian

[Markus Heukelom]

On Tue, Oct 6, 2020 at 7:45 PM Ian Lance Taylor <ia...@golang.org> wrote:

On Tue, Oct 6, 2020 at 6:32 AM Markus Heukelom <markus....@gain.pro> wrote:
>
> It appears to me the current proposal does not allow you to write a function that sorts an array of any size:
>
> func SortArray[T comparable](array [??]T, less func(a, b T) bool) [??]T {}
>
> Is it correct that this is not possible? Or is this expressed differently?
>
> To clarify, I am seeking for something like:
>
> func SortArray[T comparable, int n](array [n]T, less func(a, b T) bool) [n]T {}

You are correct that the current design draft does not provide any
mechanism for writing code that is generic across the dimension of an
array.  This is mentioned in the list at
https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#omissions.

Thanks, I missed this sentence. 

I don't think it would be hard to add later if it seems useful.

Thanks, this is good to know. Because arrays are simpler types than slices (slices are built using arrays), it would indeed make sense to add this support (or at least at some point). Otherwise wrt generics, arrays would be sort of second class, so to speak :)

That said, I don't think your suggested SortArray function would be a good API.  In Go arrays are passed by value, so this would copy the

entire array into the function, sort it, and then copy the entire
array out.  It is trivial to turn an array into a slice, by writing
a[:], so it would be more natural in Go to write Sort(a[:], less),
which would let the caller decide whether to make a copy or not

I agree. But if you need both the original and the sorted array, it could make sense. It was just meant as an example though.

I was trying around with arrays and generics because slices are more complex to reason about than arrays. For example, I introduced bugs into my code by not being fully aware of slices overwriting original data when you append to them and the capacity is not set correctly. So, when writing critical code it could be safer to avoid slices if possible for this reason. Another example:

type block[T interface{}] struct {

    next *block[T]

    used int

    items [BLOCKSIZE]T

}

Of course, items can be a slice here. But an array is simpler, and maybe block is part of a container that is an alternative to slices. However, BLOCKSIZE would be logical to make configurable and then you need to be able to write methods that deal with  [BLOCKSIZE]T, or at least  [.]T, where [.]T means "an array of T of any size". 

[Howard C. Shaw III]

You said: 

I was trying around with arrays and generics because slices are more complex to reason about than arrays. For example, I introduced bugs into my code by not being fully aware of slices overwriting original data when you append to them and the capacity is not set correctly. So, when writing critical code it could be safer to avoid slices if possible for this reason. Another example:

In my experience, you either have a fixed array size in mind to begin with (as in a fixed array size in a struct for padding or matching a fixed size C array) or you should be using a slice anyway. 

The trouble mostly comes when you keep the array around after making a slice of it. If you are  going to be doing *any* manipulation of a slice, abandoning the underlying array and only carrying around slices gets rid of most such errors. A slice already IS effectively an 'array, generic on size.'

[Markus Heukelom]

Hm, abandoning the underlying array does not really help I think:

u := []byte{0, 1, 2, 3}   

a := u[0:2]
b := u[2:]

u = nil  // abandon u

a = append(a, 4)
fmt.Println(b) // [4, 3]!! not intended

Should be:

u := []byte{0, 1, 2, 3}   
a := u[0:2:2] // use correct capacity!
b := u[2:len(u)] // use correct capacity!

u = nil // abandon u

a = append(a, 4)
fmt.Println(b) // [2, 3], ok!

Btw, I am not saying fixed arrays are a solution for this of course and I agree it is not a big problem in practice as otherwise slices are really handy.

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/MF1UzRrx9mU/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/08fe15f5-dff1-4651-b824-86266b3ce50bn%40googlegroups.com.