Type-classes are nothing like interfaces
A beginner is confused about Haskell’s type-classes and so asks the question, “What is a type-class?” The response is often devastating, “You know, like Java or C# interfaces.” This wildly misleading statement can leave the beginner in a state of disrepair. I’ll tell you why but first I must emphasise.
Type-classes are nothing like interfaces (emphasis on nothing).
Haskell has something like interfaces. They are called data types and are expressed using the data or newtype keywords. Languages like Java/C# have nothing like type-classes; there is not even a close analogy. Consider for example, Java’s Comparator interface. We would express this in Haskell like so:
newtype Comparator a = C { compare :: a -> a -> Int }
Then if we wanted to sort a list, the type would be sort :: Comparator a -> [a] -> [a]. Notice the explicit passing of the Comparator that would be required at the call site. This is just like Java.
Now suppose we did something that Java cannot do. We used a type-class.
class Comparator a where compare :: a -> a -> Int
The type for sorting a list now becomes sort :: Comparator a => [a] -> [a]. This is just like the previous signature except for the way the left-most arrow is written. This is an important distinction. When the caller uses this function, it implicitly passes the Comparator. Also, the type-class instance is decoupled from the data type. These are essential properties of type-classes. Indeed, it is its single-most defining property and since Java/C# have nothing like this, then it has nothing like type-classes.
Scala has implicit parameters which give you the ability to implement the essential property of type-classes (and more). Therefore, Scala does have something very much like type-classes. This is evident in a library such as Scalaz.
But let’s try to save the idea.
Java has implicit type-conversion by virtue of inheritance. For example, a method that accepts a T can be passed a U and its implicit conversion to a T is denoted by the way of U extends T. Notice that no side-effect can be performed during this conversion. This is unlike Scala’s implicit where it’s simply a bad idea, not enforced (Scala also has inheritance like Java).
So, if you are to say type-classes are like anything in these languages, it’s sort-of-like-yeah-ok-not-really inheritance. However, I’m sure you’ll agree, this will only cause confusion for the poor beginner, so it’s best not to draw the analogy at all.
Type-classes are a new concept to people coming from Java/C#. It is most appropriate to explain it as a new concept. I often use the contention between using java.util.Comparable, where the caller has the convenience of implicitly pass the implementation by way of inheritance but inconvenience of carrying the implementation with the data type versus using java.util.Comparator where the caller has the convenience of decoupling the implementation from the data type but requiring explicit passing at the call site. Type-classes (and Scala implicits) resolve this contention with a new concept.
April 2nd, 2010 at 8:50 am
When the caller uses this function, it implicitly passes the Comparator. Also, the type-class instance is decoupled from the data type. These are essential properties of type-classes. Indeed, it is its single-most defining property and since Java/C# have nothing like this, then it has nothing like type-classes.
—
How is different in the least from using a generic interface in C#? For example:
interface ISendable {
int Send (T arg, T arg2);
}
How is this not decoupled from the type? How is this SO different from typeclasses? Can you be more clear about the concrete difference? You kind of circle a point, then say we shouldn’t talk about that, and then ramble? It seems like there isn’t anything special about typeclasses themself but rather the way some functional languages handle type inference/polymorphism.
April 2nd, 2010 at 9:56 am
Hello Jameson,
I have assumed an understanding of type-classes in this post. The point I am addressing is regarding teaching newcomers about the concept and that I believe that the analogy to regular interfaces is detrimental to progress.
As for your question, your implementing class carries its
ISendablewith it. This is unlike type-classes where they are distinct. One of the most prominent implications of this is that you can effectively allow a class to “implement an interface” after the fact i.e. you needn’t modify the class nor the interface.One of the consequences of this, is that in your
ISendable, the type argumentTappears in all abstract methods (although there is only one). For type-classes this is enforced, though this is just an implication of the difference, not the difference itself.I hope this helps.
PS:
ISendableis a contravariant functor (if you’re interested in C# 4.0) e.g. it is possible define this method:April 9th, 2010 at 4:23 am
Whether it is detrimental to teach type classes by analogy to interfaces is purely a pedagogical question.
But there is definitely some analogy which is hard to deny: you declare some functions of certain types to exist and define some functionality based on this abstraction alone.
There is more to type classes than that, but on some (quite deep conceptual) level, this parallel is clearly worth noting, so “nothing like interfaces” is a huge overstatement.
April 9th, 2010 at 12:54 pm
Christian, I explained exactly why type-classes are nothing like interfaces. It seems you missed it. There is no parallel to “worth noting.”
April 10th, 2010 at 3:40 am
Great factual answer. Finally, you convinced me.
April 10th, 2010 at 12:10 pm
Christian,
An essential property of type-classes is the implicit dictionary passing. In the absence of this, you have a regular data type. Interfaces do not have implicit dictionary passing and are precisely equivalent to a regular data type. Interfaces do not have the key essential property that makes type-classes distinct: implicit dictionary passing. Without implicit dictionary you have regular data types, which are exactly equivalent to interfaces. Interfaces are exactly like data types. Data types are distinguished from type-classes by virtue of the requirement for explicit passing. Type-classes have implicit dictionary passing. Without implicit dictionary passing, type-classes would be something else, such as data types.
Hope that helps.
April 13th, 2010 at 10:50 am
Thanks
You also note in the last section of your post dictionary passing and implicit type conversion happens in java (to some extent) for interfaces via the inheritance mechanism.
So the difference is rather that in the case of type classes you have to define the adherence to the interface at the place of the declaration of the data type, whereas in the the case of type classes it can happen more flexibly in a decoupled way (as you note it in the same section).
I definitely agree with you that equating type classes to interfaces is a very bad idea from an educational point of view, since it would mainly focus on the commonalities rather than the important differences.
BTW, in my view implicit conversion is really not so different from inheritance either. the main difference being the decoupled nature of declaration: if there would be a fully transitive system of implicit conversions, you could easily emulate inheritance, but not vica versa.
OTOH, type classes are more restrictive than arbitrary type conversions (which is a great thing IMO), so with the same logic as this post, you could also blog “Type conversions are nothing like type classes”. Whereas in my view, there is a continuum:
interfaces < type classes < type conversions
of increasingly flexible solutions.
April 13th, 2010 at 8:14 pm
Indeed. I have been meaning to write a post about the relationship between implicit conversion (ala Scala) and inheritance. There are some key differences between the two and especially, differences with practical implications, but there are also many insightful similarities that can be used in such a way as to say “implicit conversion is not as foreign as may seem, if you are perfectly comfortable with the idea of inheritance”.
I also think this is beneficial in terms of the strong aversion to syntax such as
A => Byet there is no such aversion when the arrow is pointing upward as in inheritance (i.e. as a hint: they are the same arrow! just tilt your head 90 degrees if it helps!). This also draws on the concept of logical implication and the relationship to programming (Curry-Howard Correspondence).So many things to say
April 15th, 2010 at 4:46 am
Presumably, a type ‘a can have more than one comparator. What is the mechanism for choosing between them?
In Scala, only one implicit can be in scope else the implicit must be passed, well, explicitly. Is there something similar in Haskell?
April 15th, 2010 at 7:43 am
Hi Dan,
In Haskell it is generally considered poor form to instance a type-class more than once for a type. For example, the boolean ||/True and the &&/False monoid.
It is recommended instead to “newtype” the type then instance that, requiring the user to wrap/unwrap depending which instance they’d like to use. This is quite clumsy, but I’ve not seen a better solution to this problem.
April 16th, 2010 at 2:35 am
Also, for example, the Product and Sum monoids on integers? There was a good example of differentiating between the two on sigfpe a while back: [http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html].
In that example, one assigns an existing class to a type class using the instance keyword. You’re suggesting that one first duplicate an existing class (eg, newtype another_name_for_type = original_type) then use instance on another_name_for_type?
That makes sense; it solves the explicit-implicit problem just as well.
Thanks!
April 16th, 2010 at 10:41 am
Yes Dan, this is exactly correct.
April 30th, 2010 at 6:07 pm
How about C#’s generic type constraints? Something like:
public static Sort<T>(this IEnumerable<T> xs) where T : IComparable<T> { … }
notice the “IComparable<T>” as opposed to “IComparator<T>”, where the objects being sorted know how to sort themselves, thus “implicit”