How to express type of "slice of (string or 'other such slice')"

Question

How can I express in Go a type which is "a list of (strings or other such lists)"? Basically the good ol' "tree represented as infinitely nested lists of lists and something as values (strings in this example)"

I'm looking for the simplest possible representation of an S-expression (which itself would be the simplest of an AST), which in Python would look like this:

sexp1 = ["+", "x", "y", ["*", "10", "myVal"]]
sexp2 = ["foo" "bar" "baz"]
sexp3 = [ [ [["gooo"], "moo"] ], "too", ["yoo", "2"] ]

What type would all these expressions have in Go? Obviously [][]string doesn't work, as this doesn't work:

func makeSexp(parserName string, values ...[][]string) [][]string {
    return append([]string{parserName}, values...)
}

(Compile errors: 1. cannot use values (type [][][]string) as type []string in append, 2. cannot use append([]string literal, values...) (type []string) as type [][]string in return argument.)

...while the fully untyped version works (but I don't want to completely give up type safety!):

func makeSexp(parserName string, values ...interface{}) interface{} {
    return append([]interface{}{parserName}, values...)
}

Answer 1

Unfortunately, Go doesn't support algebraic data types, so your best bet to make it type-safe is to create an unexported interface, and make two implementations of it:

type sExp interface {
    sExp()
}

type s string

func (s) sExp() {}

type l []sExp

func (l) sExp() {}

// ...
var sexp1 sExp = l{s("+"), s("1"), s("2"), l{s("*"), s("10"), s("myVal")}}

This is basically how Protobuf compilers deal with e.g. oneof cases. This will still need a lot of type switches or type assertions to work with, but at least you can be sure that nothing outside of your module will be able to tinker with it.

Playground: https://play.golang.org/p/KOvFqJEvxZ.