How do I get around Go not having parametric polymorphism?

Question

I'm a Go newcomer, but I have read that Go regulars do not miss parametric polymorphism. Every time I try to learn a new language I use the L99 list of problems to get some practice.

Even if I try to write something as trivial as the first problem (which in Go would be a single statement, taking the last element of a slice), how would I write this as a function that takes a slice of any type and (using that single statement I referenced above) returns the last element of that slice?

I figured even though the language does not have parametric polymorphism there must be some idiomatic 'Go' way of doing this in order for Go regulars to claim they dont miss parametric polymorphism. Otherwise, if the example were more complex than just the last element of a list for instance, you would need a function to perform your task for every type.

What am I missing?

Offcenter

This question is in the same area as yours: #7743135 – Ronn

The L99 link doesn't work, can you update it? – Transport

The correct URL is: ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/… – Imperturbable

Go may have parametric polymorphism soon. See "Featherweight Go" by Robert Griesemer arxiv.org/pdf/2005.11710.pdf. – Decent

Answer 1

You cite the "99 lisp problems", yet Lisp does not have parametric polymorphism or static types at all.

Many statically-typed languages, like Objective-C, and Java before generics, have no parametric polymorphism. The solution is to just use a type that can accept all values, which in Go is interface{}, and cast when you need to get some specific type out of it.

For your specific question, how to take "any type of slice"; unfortunately, there is no interface that includes specifically slices, since slices do not have any methods; so you'll be stuck with using interface{}. Since you have an unknown slice type, you need to use reflection (the reflect package) to perform all the slice operations, including getting the length and capacity, appending, and accessing the element at a particular index.

Another alternative is that instead of using "slice of any type", just use "slice of interface{}" i.e. []interface{}, in all your code, then you can use the normal slice operators on it, and you can put any elements in, but cast when you get them out.

Noami

thank you for this information, i will give this a try tonight and see if i can make it work. – Offcenter

Clojure has parametric polymorphism. And, as far as I know Common Lisp at least has some type of dynamic dispatch. – Corncrib

Isn't []interface{} quite slow? – Kirst

Languages without parametric polymorphism (or replacement) are not really statically typed. It's like fakey types. – Upsydaisy

Answer 2

The Go way of how to return the last element of a slice is to simply write it inline as an expression. For example:

var a []int
...
last := a[len(a)-1]

Encapsulating the simple expression a[len(a)-1] into a generic function is an unnecessary complication.

Unlike Lisp, Go isn't a purely functional language. Evaluating Go based on a list of 99 Lisp problems may be deceiving. Go is a "systems programming language" - list manipulation, meta-programming, symbolic AI, or other Lisp-suited tasks aren't Go's strong sides.

I view Go as an improved C with garbage-collection and concurrency. Go isn't here to compete with Lisp.

Zeller

this is what i realized about 14 seconds ago... haha. i tried what was suggested above (using some pointers from this site -- blog.golang.org/2011/09/laws-of-reflection.html ) and while i think it might be possible to do what i want, i sure cant figure it out (and as you stated, it is certainly overly complicated). i think my usual practice of using those problems as a learning tool just fails here. – Offcenter

Note that it would also fail if you for example were learning C. Lisp is just a very different language, and the kinds of problems that make sense in Lisp might not make so much sense in Go, taking the last element of any slice in Go is so simple that it makes no sense to write a 'generic' function to do it. – Cardwell

Just a nit-pick : I would not consider Go to be a systems programming language. Go does not have enough mid-level language functionality or conditional compilation tools. And Go does not play well with other languages. Go is designed for, and excels at, writing multi-threaded servers suitable for running in a controlled corporate environment. I.e. Go is a replacement for Java or Erlang, not C or C++. Go competes with C++ only in that it's existence discourages people from using C++ for inappropriate tasks. – Kirst

Answer 3

This sounds a lot like when I discovered I was writing the same code multiple times for different arrays of different types in other programming languages like C, fpc, or delphi. I invented parametric polymorphism for a language that will probably never have it implemented, using preprocessor tricks and called it "include file parametric polymorphism" as a proof of concept that you could in fact implement parametric polymorphism into a procedural language without needing OOP or any complex generics system. Using the preprocessor is a form of abuse though, it was just to prove the concept with FPC.

Since Golang doesn't use a preprocessor, you'll have to use interfaces or pointers and send the type in as a parameter. But even using pointers still means you have to write a lot of code to cast it and make it all work. Interfaces are better than pointers because pointers are less safe.

Solutions like this:

last := a[len(a)-1]

Are prone to bugs because someone may forget the minus 1. Some languages have something slightly better:

// return last element, the "high" of a
last := a[high(a)]
// return first element, the "low" of a
first := a[low(a)]

Above code doesn't work in Go AFAIK (haven't researched whether go has something similar to this), it's just what some other languages have (fpc) that might be something Go considers.

This low and high way of dealing with things absolutely ensures the last and first element are chosen whereas using "minus one" is prone to making basic math errors. Someone may forget the minus one...because they got confused about 1 based array, versus zero based arrays. Even if the language doesn't have a such thing as a 1 based array, one could still make the error due to humans sometimes thinking in 1 based ways (our fingers start at 1, not 0). Some clever programmers would argue that, no, our fingers start at zero, not one. Your thumb is zero. Okay, fine.. but.. for most of the world...;-) we end up switching back and forth our brains from 1 based to 0 based all day long in the real world vs the computer world, and this causes numerous bugs in software.

But some would argue "Low" and "High" are just syntactic sugar that is not necessary in a minimal language. It has to be decided whether the extra safety is worthwhile, which in many cases it can be. How much complexity LOW() and HIGH() adds to a compiler I'm not sure, and how it affects performance.. I'm not 100 percent sure... I think the compiler can be smart about optimizing high and low, but I'm not certain.

Dall

Answer 4

Just answering the question of how to get the last (and first) element of an array, this is the proper way in Go:

last := a[:1] first := a[1:]

But this has nothing to do with parametric polymorphism, that is type inference and is computed at compile time.

I am in the process of attempting to write a binary tree library and I'm still struggling with the most efficient and readable and performant way to abstract a data type, specifically, I have the store, the cursor and index map system written, and walk functions, but I want to be able to switch out the data type that is actually stored in the nodes. I learned a lot about composition and embedding in the process but it's not making me completely happy.

I do know a little of the principles of functional programming and Go happens to treat functions as first class so in theory there probably is a functional solution to the parametric polymorphism issue. I am in the process of figuring it out because basically I love the Functional paradigm, but I hate recursion anyway (I prefer iteration, 100x easier for me to visualise).

Fishplate