What's the difference between parametric polymorphism and higher-kinded types?

Question

I am pretty sure they are not the same. However, I am bogged down by the common notion that "Rust does not support" higher-kinded types (HKT), but instead offers parametric polymorphism. I tried to get my head around that and understand the difference between these, but got just more and more entangled.

To my understanding, there are higher-kinded types in Rust, at least the basics. Using the "*"-notation, a HKT does have a kind of e.g. * -> *. For example, Maybe is of kind * -> * and could be implemented like this in Haskell.

data Maybe a = Just a | Nothing

Here,

• Maybe is a type constructor and needs to be applied to a concrete type to become a concrete type of kind "*".
• Just a and Nothing are data constructors.

In textbooks about Haskell, this is often used as an example for a higher-kinded type. However, in Rust it can simply be implemented as an enum, which after all is a sum type:

enum Maybe<T> {
    Just(T),
    Nothing,
}

Where is the difference? To my understanding this is a perfectly fine example of a higher-kinded type.

1. If in Haskell this is used as a textbook example of HKTs, why is it said that Rust doesn't have HKT? Doesn't the Maybe enum qualify as a HKT?
2. Should it rather be said that Rust doesn't fully support HKT?
3. What's the fundamental difference between HKT and parametric polymorphism?

This confusion continues when looking at functions, I can write a parametric function that takes a Maybe, and to my understanding a HKT as a function argument.

fn do_something<T>(input: Maybe<T>) {
    // implementation
}

again, in Haskell that would be something like

do_something :: Maybe a -> ()
do_something :: Maybe a -> ()
do_something _ = ()

which leads to the fourth question.

4. Where exactly does the support for higher-kinded types end? Whats the minimal example to make Rust's type system fail to express HKT?

Related Questions:

I went through a lot of questions related to the topic (including links they have to blogposts, etc.) but I could not find an answer to my main questions (1 and 2).

1. In Haskell, are "higher-kinded types" *really* types? Or do they merely denote collections of *concrete* types and nothing more?
2. Generic struct over a generic type without type parameter
3. Higher Kinded Types in Scala
4. What types of problems helps "higher-kinded polymorphism" solve better?
5. Abstract Data Types vs. Parametric Polymorphism in Haskell

Update

Thank you for the many good answers which are all very detailed and helped a lot. I decided to accept Andreas Rossberg's answer since his explanation helped me the most to get on the right track. Especially the part about terminology.

I was really locked in the cycle of thinking that everything of kind * -> * ... -> * is higher-kinded. The explanation that stressed the difference between * -> * -> * and (* -> *) -> * was crucial for me.

Answer 1

Some terminology:

• The kind * is sometimes called ground. You can think of it as 0th order.
• Any kind of the form * -> * -> ... -> * with at least one arrow is first-order.
• A higher-order kind is one that has a "nested arrow on the left", e.g., (* -> *) -> *.

The order essentially is the depth of left-side nesting of arrows, e.g., (* -> *) -> * is second-order, ((* -> *) -> *) -> * is third-order, etc. (FWIW, the same notion applies to types themselves: a second-order function is one whose type has e.g. the form (A -> B) -> C.)

Types of non-ground kind (order > 0) are also called type constructors (and some literature only refers to types of ground kind as "types"). A higher-kinded type (constructor) is one whose kind is higher-order (order > 1).

Consequently, a higher-kinded type is one that takes an argument of non-ground kind. That would require type variables of non-ground kind, which are not supported in many languages. Examples in Haskell:

type Ground = Int
type FirstOrder a = Maybe a  -- a is ground
type SecondOrder c = c Int   -- c is a first-order constructor
type ThirdOrder c = c Maybe  -- c is second-order

The latter two are higher-kinded.

Likewise, higher-kinded polymorphism describes the presence of (parametrically) polymorphic values that abstract over types that are not ground. Again, few languages support that. Example:

f : forall c. c Int -> c Int  -- c is a constructor

The statement that Rust supports parametric polymorphism "instead" of higher-kinded types does not make sense. Both are different dimensions of parameterisation that complement each other. And when you combine both you have higher-kinded polymorphism.

Answer 2

A simple example of what Rust can't do is something like Haskell's Functor class.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

-- a couple examples:
instance Functor Maybe where
    -- fmap :: (a -> b) -> Maybe a -> Maybe b
    fmap _ Nothing  = Nothing
    fmap f (Just x) = Just (f x)

instance Functor [] where
    -- fmap :: (a -> b) -> [a] -> [b]
    fmap _ []     = []
    fmap f (x:xs) = f x : fmap f xs

Note that the instances are defined on the type constructor, Maybe or [], instead of the fully-applied type Maybe a or [a].

This isn't just a parlor trick. It has a strong interaction with parametric polymorphism. Since the type variables a and b in the type fmap are not constrained by the class definition, instances of Functor cannot change their behavior based on them. This is an incredibly strong property in reasoning about code from types, and where a lot of where the strength of Haskell's type system comes from.

It has one other property - you can write code that's abstract in higher-kinded type variables. Here's a couple examples:

focusFirst :: Functor f => (a -> f b) -> (a, c) -> f (b, c)
focusFirst f (a, c) = fmap (\x -> (x, c)) (f a)

focusSecond :: Functor f => (a -> f b) -> (c, a) -> f (c, b)
focusSecond f (c, a) = fmap (\x -> (c, x)) (f a)

I admit, those types are beginning to look like abstract nonsense. But they turn out to be really practical when you have a couple helpers that take advantage of the higher-kinded abstraction.

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    -- fmap :: (a -> b) -> Identity a -> Identity b
    fmap f (Identity x) = Identity (f x)

newtype Const c b = Const { getConst :: c }

instance Functor (Const c) where
    -- fmap :: (a -> b) -> Const c a -> Const c b
    fmap _ (Const c) = Const c

set :: ((a -> Identity b) -> s -> Identity t) -> b -> s -> t
set f b s = runIdentity (f (\_ -> Identity b) s)

get :: ((a -> Const a b) -> s -> Const a t) -> s -> a
get f s = getConst (f (\x -> Const x) s)

(If I made any mistakes in there, can someone just fix them? I'm reimplementing the most basic starting point of lens from memory without a compiler.)

The functions focusFirst and focusSecond can be passed as the first argument to either get or set, because the type variable f in their types can be unified with the more concrete types in get and set. Being able to abstract over the higher-kinded type variable f allows functions of a particular shape can be used both as setters and getters in arbitrary data types. This is one of the two core insights that led to the lens library. It couldn't exist without this kind of abstraction.

(For what it's worth, the other key insight is that defining lenses as a function like that allows composition of lenses to be simple function composition.)

So no, there's more to it than just being able to accept a type variable. The important part is being able to use type variables that correspond to type constructors, rather than some concrete (if unknown) type.

Answer 3

I'm going to resume it: a higher-kinded type is just a type-level higher-order function.

But take a minute:

Consider monad transformers:

newtype StateT s m a :: * -> (* -> *) -> * -> *

Here,

- s is the desired type of the state
- m is a functor, another monad that StateT will wrap
- a is the return type of an expression of type StateT s m

What is the higher-kinded type?

m :: (* -> *)

Because takes a type of kind * and returns a kind of type *.

It's like a function on types, that is, a type constructor of kind

* -> *

In languages like Java, you can't do

class ClassExample<T, a> {
    T<a> function()
}

In Haskell T would have kind *->*, but a Java type (i.e. class) cannot have a type parameter of that kind, a higher-kinded type.

Also, if you don't know, in basic Haskell an expression must have a type that has kind *, that is, a "concrete type". Any other type like * -> *.

For instance, you can't create an expression of type Maybe. It has to be types applied to an argument like Maybe Int, Maybe String, etc. In other words, fully applied type constructors.

Answer 4

Parametric polymorphism just refers to the property that the function cannot make use of any particular feature of a type (or kind) in its definition; it is a complete blackbox. The standard example is length :: [a] -> Int, which only works with the structure of the list, not the particular values stored in the list.

The standard example of HKT is the Functor class, where fmap :: (a -> b) -> f a -> f b. Unlike length, where a has kind *, f has kind * -> *. fmap also exhibits parametric polymorphism, because fmap cannot make use of any property of either a or b in its definition.

fmap exhibits ad hoc polymorphism as well, because the definition can be tailored to the specific type constructor f for which it is defined. That is, there are separate definitions of fmap for f ~ [], f ~ Maybe, etc. The difference is that f is "declared" as part of the typeclass definition, rather than just being part of the definition of fmap. (Indeed, typeclasses were added to support some degree of ad hoc polymorphism. Without type classes, only parametric polymorphism exists. You can write a function that supports one concrete type or any concrete type, but not some smaller collection in between.)