Recursive slice type definition. type N []N

Question

I stumbled upon a recursive type definition in this question:

type N []N

As I understand, it defines a type with a name N that is a slice of an array of type N, meaning this type definition is recursive.

What is the rationale behind treating this code as valid?

What are some examples with a use case for this?

I tried to experiment with this:

package main

import "fmt"

type N []N

func main() {
    var n N
    fmt.Printf("Naked:   %T %v\n", n, n)
    n = make(N, 1)
    fmt.Printf("First:   %T %v\n", n, n)
    n[0] = make(N, 1)
    fmt.Printf("Second:  %T %v %T %v\n", n, n, n[0], n[0])
    n[0][0] = make(N, 1)
    fmt.Printf("Third:   %T %v %T %v %T %v\n", n, n, n[0], n[0], n[0][0], n[0][0])
    n[0] = n
    fmt.Println("Drum roll")
    fmt.Printf("Blatant: %T %v %T %v\n", n, n, n[0], n[0])
    fmt.Println("Reached the main end")
}

Running this code didn't give me any answers, only more questions:

• It's ok to create a variable of such type
• Ok to access and change elements of a variable of such a type
• Examine the type of such a variable (at least with Printf)

port Naked:   main.N []
First:   main.N [[]]
Second:  main.N [[[]]] main.N [[]]
Third:   main.N [[[[]]]] main.N [[[]]] main.N [[]]
Drum roll
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc020160358 stack=[0xc020160000, 0xc040160000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x49ae35?, 0x518860?})
    /usr/lib/go/src/runtime/panic.go:1047 +0x5d fp=0xc0004b1e10 sp=0xc0004b1de0 pc=0x43177d
runtime.newstack()
    /usr/lib/go/src/runtime/stack.go:1103 +0x5cc fp=0xc0004b1fc8 sp=0xc0004b1e10 pc=0x448e2c
runtime.morestack()
    /usr/lib/go/src/runtime/asm_amd64.s:570 +0x8b fp=0xc0004b1fd0 sp=0xc0004b1fc8 pc=0x45ae4b

goroutine 1 [running]:
runtime.assertE2I2(0x48dae0?, {0x48b200?, 0xc001d16918?})
    /usr/lib/go/src/runtime/iface.go:456 +0x78 fp=0xc020160368 sp=0xc020160360 pc=0x409c78
fmt.(*pp).handleMethods(0xc000118270, 0x116018?)
    /usr/lib/go/src/fmt/print.go:621 +0xdd fp=0xc0201605b8 sp=0xc020160368 pc=0x47dd1d
fmt.(*pp).printValue(0xc000118270, {0x48b200?, 0xc000116018?, 0x0?}, 0x76, 0x10841b)
    /usr/lib/go/src/fmt/print.go:754 +0xe5 fp=0xc0201607a8 sp=0xc0201605b8 pc=0x47ed45
fmt.(*pp).printValue(0xc000118270, {0x48b200?, 0xc000116018?, 0x0?}, 0x76, 0x10841a)
    /usr/lib/go/src/fmt/print.go:896 +0x16b2 fp=0xc020160998 sp=0xc0201607a8 pc=0x480312
fmt.(*pp).printValue(0xc000118270, {0x48b200?, 0xc000116018?, 0x0?}, 0x76, 0x108419)
    /usr/lib/go/src/fmt/print.go:896 +0x16b2 fp=0xc020160b88 sp=0xc020160998 pc=0x480312"fmt"

While trying to clear this up, I read through this question about recursive function definitions. type Func func()(int int Func) I do understand, but it seems distinct from the N definition in that it is used in tandem with a definition of an actual function of that type that can call self.

It seems, while I was writing this question, I started to understand the behavior of the code above:

• Declaring a variable n has to allocate memory on the spot only to pointer to the array, the length of the segment, and its capacity
• When n[0] is initialized, an array of tuples (ptr,len,cap) is created, the size of which is independent of the stored elements type
• Initializing n[0][0] does the same, resulting in slice of slice of slice with nullptr for the array pointer of the innermost slice
• Because of this, reflection in Printf works fine, and value of n expectedly keeps changing from "empty slice" to "slice of one empty slice" to...
• That is when n[0] = n arms a landmine: it makes ptr of n[0] point to n, creating a loop in the nesting of the slices
• Instructing Printf to figure out the type of n makes it recursively chase that loop and overflow the stack.

But all this doesn't answer the question, what can this be used for? Or is it an unintended quirk in language that should be stayed clear of?

Answer 1

I think you're getting tripped up on the cycles. Those might be possible, but in general I think pointers are a better idea. When reasoning about recursive objects, I find it helpful to first understand the terminating case. In your example, that would be nil.

So once you have that, you can easily create an object using the new type. Here is a working example based on your code, minus the cycle:

package main

import "fmt"

type N []N

func main() {
   n := N{
      N{
         N{nil},
      },
   }
   fmt.Println(n) // [[[[]]]]
}