Scala: Higher kinded, open-type and wild card generics in Java, C#, Scala and C++

11
votes

I'd been programming in C#, but was frustrated by the limitations of its type system. One of the first things, I learned about Scala was that Scala has higher kinded generics. But even after I'd looked at a number of articles, blog entries and questions I still wasn't sure what higher kinded generics were. Anyway I'd written some Scala code which compiled fine, Does this snippet use higher kinds?

abstract class Descrip [T <: DTypes, GeomT[_ <: DTypes] <: GeomBase[_]](newGeom: NewGeom[GeomT])
{
  type GeomType = GeomT[T]
  val geomM: GeomT[T] = newGeom.apply[T]()  
}

And then I thought maybe I'm already using higher kinded generics. As I understand it I was, but then as I now I understand it I had already been happily using higher kinded types in C# before I'd even heard of Scala. Does this snipet use higher kinded type?

namespace ConsoleApplication3
{
    class Class1<T>
    {
        List<List<T>> listlist;
    }
}

So to avert further confusion I thought it would be useful to clarify for each of Java, C# and Scala what they allow in terms of Higher kinded types, wild cards and the use of open / partially open types. As the key difference between C# and Scala seems to be that Scala allows wild cards and open types, where as C# has no wild card and requires all generic types to be closed before use. I know they are some what different but I think it would be useful to relate the existence of these features to their equivalent in C++ Templates.

So is the following correct? This table has been corrected for Alexey's answer

Lang:   Higher-kind Wild-card Open-types

Scala    yes         yes       yes

C#       no          no        no

Java     no          yes       no

C++      yes         yes       yes
2
c#javac++scalagenerics
Is the table at the bottom correct? If anyone can format it better please do? – Rich Oliver
What you have writen in C# is available in java, and not Higher kinded. Your class with the GeomT parameter above is. See stackoverflow.com/a/10499788/754787. – Didier Dupont
@didierd Well if you're correct I'm still confused because I don't understand why the example in Dan Burton's Answer of referenced question is higher-kinded and the C# example is not. I realise there is some overlap with previous questions but I feel a more definitive clarification of generics could save a lot of time for learners. – Rich Oliver
I think it's much clearer to talk about type constructors. It's a "function" that takes a type and produces a type. – Jesper Nordenberg

2 Answers

9
votes

This is higher kinded type is it not:

No. A higher-kinded type is something like 

class Class1<T>
{
    T<String> foo; // won't compile in actual C#
}

I.e. a generic type whose parameters are required to be generic themselves. Note that in this example Class1<IList> should compile, but Class1<String> or Class1<IDictionary> should not.

8
votes

It seems you need to understand what higher kinded types are, and why they are useful.

Consider the following interfaces (Java, F<X,Y> used as closure replacement):

interface ListFun {
   public <A,B> List<B> fmap(F<A,B> fn, List<A> list);
}

interface SetFun {
   public <A,B> Set<B> fmap(F<A,B> fn, Set<A> set);
}

The interfaces look useful, as they define a kind of "transformation" for collections (this is called a "functor"). But they look pretty much like code duplication. But you can't write a "unified" interface, neither in Java nor in C#.

How should it look like? You would be tempted to write something like

interface Fun<X> {
   public <A,B> X<B> fmap(F<A,B> fn, X<A> col);
}

class ListFun implements Fun<List> {...}

But X<A> is not allowed in Java or C#, if X is not a fixed type like List, but a type parameter. But if this abstraction is allowed in some way (like in Scala or Haskell), you have higher kinded types (or "higher order type polymorphism", the terminology is still murky for this). Here is the Scala trait and an implementation:

trait Fun[X[_]] {
  def fmap[A,B](fn: A => B, col:X[A]):X[B]
}

class ListFun extends Fun[List]{
  def fmap[A,B](fn: A => B, list: List[A]) = list.map(fn)
}

That's the basic idea. Usually you don't need this stuff too often, but when you need it, it can be incredible useful.