Higher degrees of higher kinded types?

Question

I just recently learned about higher kinded types, but every example I was presented with only used a degree-2 kind (* -> *) -> *, like Functor.

In Scala, a weird trait definition is used, and in Haskell, type classes are used. And both approaches seem like they cannot work with one degree of abstraction more (i.e. ((* -> *) -> *) -> *).

I am neither an expert in Scala nor Haskell, so it would be helpful if you could provide simple examples of such higher degree types, if they are expressible at all.

Answer 1

In Scala(Z), the obvious higher-kind type is the MonadTrans trait:

trait MonadTrans[F[_ [_], _]] { ... }

Its kind is T->*, where T is the kind of its parameter F.

F is a monad transformer, and T is the kind of all monad transformers. Recall that a monad transformer is parametrised by a monad and its "output" is another monad, so its kind is (*->*) -> (*->*) (or, equivalently, (*->*) -> * -> *). So the kind of MonadTrans is

((*->*) -> * -> *) -> *

In Haskell there are no traits, and type classes are not types, so MonadTrans is out as a non-type. There is a type that represents a composition of monad transformers though:

newtype ComposeT f g m a = ...

Here's its full definition from Control.Monad.Trans.Compose:

newtype ComposeT (f :: (* -> *) -> * -> *) (g :: (* -> *) -> * -> *) m a
    = ComposeT { getComposeT :: f (g m) a }

Quite a mouthful! f and g are monad transformers (as can be seen from their explicitly given signatures), m is a monad (signature * ->* is not given explicitly but implied by g m), and a is a regular type of kind *. So the overall kind of ComposeT is:

((* -> *) -> * -> *) ->
((* -> *) -> * -> *) ->
 (* -> *) -> * -> *

Answer 2

trait Functor[F[_]] //has kind (* -> *) -> *

trait Functor[A[B[_]]] //has kind ((* -> *) -> *) -> *

trait Map[A[_],B[_]] //has kind (* -> *) -> (* -> *) -> *

Edit:

You can investigate kinds by yourself by calling "kind" command in REPL:

scala> :kind -v Map