Contrasting C# generics with Haskell parameterized types

Question

Based on some advice I found on StackOverflow, I'm digging into Haskell. I was pleased to see that Haskell's parameterized types behave very much like C# generics. Both languages advise a single letter for the type parameter (usually), and both languages seem to follow a similiar process for substituting an actual type for the type parameter. I grokked the concept pretty quickly because of that.

Which leads to this: what are some ways in which Haskell's parameterized types differ from C# generic types? I know from learning Ruby that you can get into big trouble thinking that a concept you're familiar with from one language is the same in another language you're new to. Usually, the trouble is worse when the features actually are very similar ... because they're usually not 100% the same. So what are some of the "gotchas" I might get bitten by if I assume I understand parameterized types based on my knowledge of C# generics?

Thanks.

Answer 1

Here's one difference to keep in mind:

C# has subtyping, but Haskell does not, which means, for one thing, that you know more things by simply looking at a Haskell type.

id :: a -> a

This Haskell function takes a value of a type and returns that same value of that same type. If you give it a Bool, it will return a Bool. Give it a Int, it will return a Int. Give it a Person, it will return a Person.

In C#, you can't be so sure. This is that 'function' in C#:

public T Id<T>(T x);

Now, because of subtyping you could call it like so:

var pers = Id<Person>(new Student());

While pers is of type Person, the argument to the Id function is not. In fact pers might have a more specific type than just Person. Person could even be an abstract type, guaranteeing that pers will have a more specific type.

As you can see, even with a function as simple as id the .NET type system already allows for a lot more than the stricter type system from Haskell. While that might be useful to do some programming work, it also makes it harder to reason about a program by just looking a the types of things (which is a joy to do in Haskell).

---

And a second thing, there is ad hoc polymorphism (aka overloading) in Haskell, via a mechanism known as 'type classes'.

equals :: Eq a => a -> a -> Bool

This function checks if two values are equal. But not just any two values, just the values that have instances for the Eq class. This is sort of like constraints on type parameters in C#:

public bool Equals<T>(T x, T y) where T : IComparable

There is a difference, however. For one thing, the subtyping: you could instantiate it with Person and call it with Student and Teacher.

But there is also a difference in what this compiles to. The C# code compiles to almost exactly what its type says. The type checker makes sure the arguments implement the proper interface, and than you're good.

Whereas the Haskell code complies to something like this:

equals :: EqDict -> a -> a -> Bool

The function gets an extra argument, a dictionary of all the functions it needs to do the Eq things. Here's how you could use this function, and what it compiles to:

b1 = equals 2 4          --> b1 = equals intEqFunctions 2 4
b2 = equals True False   --> b2 = equals boolEqFunctions True False

This also shows what makes subtyping such a pain, imagine if this where possible.

b3 = equals someStudent someTeacher
     --> b3 = equals personEqFunctions someStudent someTeacher

How is the personEqFunctions dictionary supposed to figure out if a Student is equal to a Teacher? They don't even have the same fields.

In short, while Haskell type constraints at first sight might look like .NET type constraints, they are implemented completely differently and compile to two really different things.

Answer 2

We can do other things with Haskell type classes too now. Googling for "generics" in Haskell opens up a whole field of higher-rank polymorphic generic programming, beyond the standard parametric polymorphism most people think of as "generics".

For example, GHC recently gained type families, enabling all sorts of interesting type programming capabilities. A very simple example is per-type data representation decisions for arbitrary polymorphic containers.

I can make a class for say, lists,

class Listy a where

    data List a 
             -- this allows me to write a specific representation type for every particular 'a' I might store!

    empty   :: List a
    cons    :: a -> List a -> List a
    head    :: List a -> a
    tail    :: List a -> List a

I can write functions that operate on anything that instantiates List:

map :: (Listy a, Listy b) => (a -> b) -> List a -> List b
map f as = go as
  where
    go xs
        | null xs   = empty
        | otherwise = f (head xs) `cons` go (tail xs)

And yet we've never given a particular representation type.

Now that is a class for a generic list. I can give particular cunning representations based on the element types. So e.g. for lists of Int, I might use an array:

instance Listy Int where

data List Int = UArray Int Int

...

So you can start doing some pretty powerful generic programming.

Answer 3

To follow up on the, "you can get into big trouble thinking that a concept you're familiar with from one language is the same in another language [to which you're new]" part of this question:

Here's the key difference (from, say, Ruby) you need to understand when you use Haskell type classes. Given a function such as

add :: Num a => a -> a -> a
add x y = x + y

This does not mean that x and y are both any types of class Num. It means that x and y are of the exact same type, which type is of class Num. "Well, of course you say; a is the same thing as a." Which I say too, but it took me many months to stop thinking that if x was an Int and y was an Integer, it would be just like adding a Fixnum and Bignum in Ruby. Rather:

*Main> add (2::Int) (3::Integer)

<interactive>:1:14:
    Couldn't match expected type `Int' against inferred type `Integer'
    In the second argument of `add', namely `(3 :: Integer)'
    In the expression: add (2 :: Int) (3 :: Integer)
    In the definition of `it': it = add (2 :: Int) (3 :: Integer)

In other words, subclassing (though both those Num instances are of course also instances of Eq) and duck typing are gone, baby.

This sounds pretty simple and obvious, but it takes quite some time to train yourself to understand this instinctively, rather than just intellectually, at least if you've come from years of Java and Ruby.

And no, once I got the hang of this, I don't miss subclassing a bit. (Well, maybe a little now and then, but I've gained much more than I've lost. And when I really miss it, I can try to misuse existential types.)

Answer 4

Another big difference is that C# generics don't allow abstraction over type constructors (i.e. kinds other than *) while Haskell does. Try translating the following datatype into a C# class:

newtype Fix f = In { out :: f (Fix f) }