If you ever use GHC, you'll notice how slowly it compiles. However, this dilemma (trilemma?) is a false one. You can have unboxed (in relevant cases) generics in a language that compiles faster than C++ with full-blown templates. C# and Ada come to mind.

Ada in particular escapes this burden by requiring explicit generic instantiation, so at least you know how many of them you're dealing with.

In the most general case it uses boxing strategies, but it's also able to behave like C++ with certain compile-time optimizations turned on (at the cost of slowing down compilation). There's a lot of literature out there about how to take advantage of those optimizations. It's a fairly involved topic.

There are a whole host of ways that Haskell supports (or has been extended to support) generic programming. There's a big overview here:

http://www.haskell.org/haskellwiki/Research_papers/Generics

In the simplest case, generic programming in Haskell is done using type classes (similar to OO "interfaces"), often with the GHC extension for derivable type classes. If I understand correctly, this is generally implemented by implicitly passing a table of type information to the generic function at runtime, though I believe that compilers are able to optimize this away at compile time in some (most?) cases.

I'm not sure how well any of this would apply to Go, which doesn't have Haskell's type system.

No, the simplest case for Haskell would be type variables. For example, the map function doesn't need typeclasses at all:

map :: (a -> b) -> [a] -> [b]

For the record, in Go+generics, this might look something like:

func map<A,B>(f func (A) B, xs A[]) B[] { ... }

Good point, I forgot that even simpler cases in Haskell are generic too.