How do you implement a container for different types in Go?

The following code implements a List of ints in Go:

package main

import "fmt"

type List struct {
    Head int
    Tail *List
}

func tail(list List) *List {
    return list.Tail
}

func main() {
    list := List{Head: 1, Tail: 
         &List{Head: 2, Tail:
         &List{Head: 3, Tail:
         nil}}}
    fmt.Println(tail(list).Head)
}

Problem is this only works for int. If I wanted a list of strings, I'd need to re-implement every list method (such as tail) again! That's obviously not practical, so, this can be solved by using an empty interface:

type List struct {
  Head interface{} // Now works for any type!
  Tail *List
}

Problem is, 1. this seems to be much slower because of type casts, 2. it throws aways type safety, allowing one to type-check anything:

// This type-checks!
func main() {
    list := List{Head: 123456789 , Tail:
         &List{Head: "covfefe" , Tail:
         &List{Head: nil       , Tail:
         &List{Head: []int{1,2}, Tail:
         nil}}}}
    fmt.Println(tail(list).Head)

Obviously that program should not type-check in a statically typed language.

How can I implement a List type which doesn't require me to re-implement all List methods for each contained type, but which keeps the expected type safety and performance?

Go doesn't have generic types, so you're stuck with the options you listed. Sorry.

> Meanwhile, Go's built-in maps and slices, plus the ability to use the empty interface to construct containers (with explicit unboxing) mean in many cases it is possible to write code that does what generics would enable, if less smoothly.

If you know more about the elements you want to store in the container, you may use a more specialized interface type (instead of the empty interface interface{}), which

• could help you avoid using type assertions (keep good performance)
• and still keep type safety
• and it can be used for all types that (implicitly) implement your interface (code "re-usability", no need to duplicate for multiple types).

But that's about it. See an example of this here: https://stackoverflow.com/questions/39092925/why-are-interfaces-needed-in-golang/39100038#39100038

Also just in case you missed it, the standard library already has a doubly linked list implementation in the container/list package (which also uses interface{} type for the values).

It's important to acknowledge that we expect generic types to be slower, not faster. The excellent fastutil library for Java outperforms the more flexible classes from the standard library by using concrete implementations.

Russ Cox (one of Go's authors) summarises the situation like this:

> * (The C approach.) Leave them out.

• This slows programmers.
• (The C++ approach.) Compile-time specialization or macro expansion.
  • This slows compilation.
• (The Java approach.) Box everything implicitly.
  • This slows execution.

You may be interested in this living document which has a lot of the pros and cons outlined.

As the other answer points out, Go does not support the design you're trying to achieve here. Personally, I'd just duplicate the code - it's not much, the tests are cheap, and most of the time you don't actually need the generic behaviour you want to implement.