Generic arguments in recursive functions

[Aidan Hahn]

Hello Go users!

I am playing with the generics that were added in go 1.18 and noticed an odd discrepancy that I have not been able to find an authoritative answer to. Consider the following data type, as well as the function defined for it:

type Node[T any] struct {
    Inner T
    Next  *Node[any]
}

func (n *Node[any]) ListPreTraverse(f func(*Node[any])) {
    tmpN := interface{}(n)
    if tmpN, ok := tmpN.(*Node[*Node[any]]); ok {
        tmpN.Inner.ListPreTraverse(f)
    } else {
        f(n)
    }
    n.Next.ListPreTraverse(f)

}

This function is a simple attempt to iterate across a generic linked list and call a function on each node in the list (although in this case it may behave more like a tree if inner stores another node). When I went to compile this code I encountered the following error:

test.go:64:25: cannot use f (variable of type func(*Node[any])) as type func(*Node[any]) in argument to n.Next.ListPreTraverse

To me at least it seems that all the information to validate that the argument fits the type specified in the function call is there, defined in the function header. What am I missing?

Thanks,
Ava

[Ian Lance Taylor]

The error message is confusing because the "any" used in
ListPreTraverse is shadowing the "any" used in Node. See
https://go.dev/doc/faq#types_in_method_declaration. You want to write

func (n *Node[T]) ListPreTraverse(f func(*Node[T])) {

But then you will see that your code has an instantiation cycle,
violating the restriction described at
https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#generic-types:
"A generic type can refer to itself in cases where a type can
ordinarily refer to itself, but when it does so the type arguments
must be the type parameters, listed in the same order. This
restriction prevents infinite recursion of type instantiation."

I don't really understand what you are trying to do here. The type
assertion doesn't make sense to me. Perhaps this is the code you
want:

type Node[T any] struct {
Inner T

Next *Node[T]
}

func (n *Node[T]) ListPreTraverse(f func(*Node[T])) {
f(n)
if n.Next != nil {
n.Next.ListPreTraverse(f)
}
}

Ian

[Aidan Hahn]

Hello Ian,

I think some of your confusion may be because the function is poorly named. In some cases the Node generic may store another Node in the generic Inner field.
In this case I want my preorder traversal to also traverse the list in the Inner field. "TreePreTraverse" would be a better name.

func (n *Node[any]) TreePreTraverse(f func(*Node[any])) {

    tmpN := interface{}(n)
    if tmpN, ok := tmpN.(*Node[*Node[any]]); ok {

        tmpN.Inner.TreePreTraverse(f)
    } else {

        f(n)
    }

    if n.Next != nil {

        n.Next.TreePreTraverse(f)
    }
}

Additionally, I notice that you set the "Next" field to *Node[T] mirroring the type of the parent Node, but part of my goal with this exercise is to be able to have a list of elements of varying type. If I set the generic type for the Next field to 'T' then the list has to be homogeneous.

Ignoring the weird corner case, I am just wondering why f, unchanged, cannot be passed into a recursion of the function that it is an argument to.

Thanks,
Ava

[Ian Lance Taylor]

On Sun, Apr 10, 2022, 11:42 AM Aidan Hahn <aidanja...@gmail.com> wrote:

Hello Ian,

I think some of your confusion may be because the function is poorly named. In some cases the Node generic may store another Node in the generic Inner field.
In this case I want my preorder traversal to also traverse the list in the Inner field. "TreePreTraverse" would be a better name.

func (n *Node[any]) TreePreTraverse(f func(*Node[any])) {

Maybe I didn't emphasize this, but don't write Node[any].  That doesn't make sense.  That is saying that the type parameter is named "any".  Write Node[T] or something similar.

Ian

--
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/019beabf-a1f5-4aeb-96d4-c121ae3c2252n%40googlegroups.com.