13

Some languages allow for classes and functions with type parameters (such as List<T> where T may be an arbitrary type). For example, you can have a function like:

List<S> Function<S, T>(List<T> list)

Some languages however allow this concept to be extended one level higher, allowing you to have a function with the signature:

K<S> Function<K<_>, S, T>(K<T> arg)

Where K<_> itself is a type like List<_> that has a type parameter. This "partial type" is known as a type constructor.

My question is, why do you need this ability? It makes sense to have a type like List<T> because all List<T> are almost exactly the same, but all the K<_> can be entirely different. You can have an Option<_> and a List<_> that have no common functionality at all.

  • 7
    There are several good answers here: stackoverflow.com/questions/21170493/… – itsbruce Mar 17 '15 at 17:17
  • 3
    @itsbruce In particular, the Functor example in Luis Casillas's answer is quite intuitive. What do List<T> and Option<T> have in common? If you give me either one and a function T -> S I can give you a List<S> or Option<S>. Another thing they have in common is that you can try to get a T value out of both. – Doval Mar 17 '15 at 17:25
  • @Doval: How would you do the former? To the extent that one is interested in the latter, I would think that could be handled by having both types implement IReadableHolder<T>. – supercat Mar 17 '15 at 21:10
  • @supercat I'm guessing they would have to implement IMappable<K<_>, T> with the method K<S> Map(Func<T, S> f), implementing as IMappable<Option<_>, T>, IMappable<List<_>, T>. So you would have to constrain K<T> : IMappable<K<_>, T> to get any use out of it. – GregRos Mar 17 '15 at 21:36
  • 1
    Casting isn't an appropriate analogy. What is done with type classes (or similar constructs) is that you show how a given type satisfies the higher kinded type. This usually involves defining new functions or showing which existing functions (or methods if its an OO language like Scala) can be used. Once this has been done, any functions defined to work with the higher type will all work with that type. But it's much more than an interface because more than a simple set of function/method signatures are defined. I guess I am going to have to go and write an answer to show how that works. – itsbruce Mar 17 '15 at 23:22
5

Since no one else has answered the question, I think I'll give it a go myself. I'm going to have to get a bit philosophical.

Generic programming is all about abstracting over similar types, without the loss of type information (which is what happens with object-oriented value polymorphism). In order to do this, the types must necessarily share some sort of interface (a set of operations, not the OO term) that you can use.

In object-oriented languages, types satisfy an interface by virtue of classes. Each class has its own interface, defined as part of its type. Since all classes List<T> share the same interface, you can write code that works no matter which T you choose. Another way to impose an interface is an inheritance constraint, and although the two seem different, they are sort of similar if you think about it.

In most object-oriented languages, List<> is not a proper type in itself. It has no methods, and thus has no interface. It is only List<T> that has these things. Essentially, in more technical terms, the only types you can meaningfully abstract over are those with the kind *. In order to make use of higher-kinded types in an object-oriented world, you have to phrase type constraints in a manner consistent with this restriction.

For example, as mentioned in the comments, we can view Option<> and List<> as "mappable", in the sense that if you have a function, you could convert an Option<T> into an Option<S>, or a List<T> into a List<S>. Remembering that classes cannot be used to abstract over higher-kinded types directly, we instead make an interface:

IMappable<K<_>, T> where K<T> : IMappable<K<_>, T>

And then we implement the interface in both List<T> and Option<T> as IMappable<List<_>, T> and IMappable<Option<_>, T> respectively. What we've done, is using higher-kinded types to place constraints on the actual (non-higher-kinded) types Option<T> and List<T>. This is how it's done in Scala, though of course Scala has features such as traits, type variables, and implicit parameters that make it more expressive.

In other languages, it is possible to abstract over higher-kinded types directly. In Haskell, one of the highest authorities on type systems, we can phrase a type class for any type, even if it has a higher kind. For example,

class Mappable mp where
    map :: mp a -> mp b

This is a constraint placed directly on an (unspecified) type mp which takes one type parameter, and requires it be associated with the function map that turns an mp<a> into an mp<b>. We can then write functions that constrain higher-kinded types by Mappable just like in object-oriented languages you could place an inheritance constraint. Well, sort of.

To sum things up, your ability to make use of higher-kinded types depends on your ability to constrain them or to use them as part of type constraints.

  • Been too busy changing jobs but finally will find some time to write my own answer. I do think you've been distracted by the idea of constraints, though. One significant aspect of higher kinded types is that they allow functions/behaviour to be defined which can be applied to any type which can logically be shown to qualify. Far from imposing constraints on existing types, type classes (one application of higher kinded types) add behaviour to them. – itsbruce Mar 23 '15 at 20:49
  • I think it's an issue of semantics. A type class defines a class of types. When you define a function such as (Mappable mp) => mp a -> mp b, you've placed a constraint on mp to be a member of the type class Mappable. When you declare a type such as Option to be an instance of Mappable, you add behavior to that type. I guess you could make use of that behavior locally without ever constraining any type, but then it's no different from defining an ordinary function. – GregRos Mar 23 '15 at 23:48
  • Also, I am quite certain type classes aren't directly related to higher-kinded types. Scala has higher-kinded types, but not type classes, and you could restrict type classes to types with the kind * without making them unusable. It's definitely true that type classes are very powerful when working with higher-kinded types, though. – GregRos Mar 23 '15 at 23:56
  • Scala has type classes. They are implemented with implicits. The implicits provide the equivalent of the Haskell type class instances. It's a more fragile implementation than Haskell's because there is no dedicated syntax for it. But it was always one of the key purposes of Scala implicits and they do the job. – itsbruce Mar 24 '15 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.