Tried the language recently. Wanted a in-memory data structure that could represent a filesystem-like graph. Ran away when I understood (please correct me if I got that wrong, but I wasted a whole weekend and found nothing) that it's either totally type-unsafe void*^H^W interface{} all the way or I have to write my own separate implementation for every and each type of graph I'll use, without any significant way to reuse code.
The types of your nodes probably don't have much to do with any algorithms you may be writing. Consider your algorithms as functions which act on an interface. Keep your graph data within a type which adheres to that interface. Then you only have to duplicate the type and not the algorithms, and you can easily create new types which the algorithms can use.
Even if you stuff the algorithms into the same type you have your data in (like most generic languages seem to encourage you to do), you still only have to type-cast/type-switch on getters and callbacks. And the only major missing requirement I can think of is that your nodes aren't guaranteed to be of homogeneous types (and you can hack that with a callback if you want).
> "The types of your nodes probably don't have much to do with any algorithms you may be writing."
Which is precisely why he wants generic types.
> "Consider your algorithms as functions which act on an interface."
How would he write a function that explicitly expects a graph whose nodes contain ints, and not, say, strings? What kind of interface would that function act upon?
> "you still only have to type-cast/type-switch on getters and callbacks."
Although I'd prefer to have generics, the issue isn't obvious. Generics can be really hard to understand. For example here's a HashMap in Scala:
class HashMap[A, B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, HashMap[A, B]] with HashTable[A, DefaultEntry[A, B]] with CustomParallelizable[(A, B), ParHashMap[A, B]] with Serializable
If that's what the type system is going to end up being with generics I'd rather just cast things. Sometimes less is more.
I don't know Scala but the very basics of the language, however notation seems clear.
Class HashMap is parametrized over two types, A and B (presumably, key and value types). The rest seems to be implementation details, that play no importance unless you're going to actually use them. Just as integers are totally ordered, but unless you have use to that fact (i.e. comparing those integers), you can safely ignore that.
Same as with interfaces - if there's a interface Foo { ... } somewhere, you don't have to care your types implement it unless you're actually using it.
One problem with that idiomatic Scala code is that all inherited traits have to be declared in the same place, making the definition conceptually "too loaded". (Scala's implicits allow for something more flexible, akin to Haskell's type classes, though.)
That suggests a problem with subtyping (or, rather, with inheritance as construct for implementing subtyping), not with generics. Parametric polymorphism is a most natural notion.
Without generics you'll need to use an alternative approach. As you said you can use interface{} everywhere. Another option is to create an interface that does what you need. Checkout "sort" for an example: http://golang.org/pkg/sort/#Interface.
Sure, I can `type Tree struct { Child []*Tree; Node NodeType }`, where `NodeType` is either `interface{}` (makes `Tree` reusable by sacrificing type safety) or some concrete type (sacrifices `Tree`'s reuse) but that's about how far I can progress. Also, I have to manually ensure that only one of Child or Node is set, but not both.
I just can't do anything like `data Tree a = Leaf a | Node [Tree a]` there.
(Edit: okay, my mind swayed a bit, that was trees, not graphs. I had different ideas on data structure to use, and my memories are a bit messy. Sorry about this. The problem should still hold, it applies to both trees and graphs, and I think many other data structures too.)
The 'one of Child or Node' isn't really an issue since you probably shouldn't expose the members of the struct (the tree should be accessed via methods). But I agree with your point about containers.
I think he already covered both, the second with "or I have to write my own separate implementation for every and each type of graph I'll use, without any significant way to reuse code".
Have you given Rust a try? As far as I understand, it supports generics and defining your own data types pretty well, although I've never tried Rust myself.
Rust's polymorphism system is somewhat limited compared to, say, (GHC) Haskell. But, to the best of my knowledge, it is the best among languages aiming at mainstream.
