The K in SemigroupK

[eed3si9n]

The Scaladoc on SemigroupK (https://github.com/typelevel/cats/blob/v0.7.2/core/src/main/scala/cats/SemigroupK.scala) says:

 * SemigroupK is a universal semigroup which operates on kinds.
 *
 * This type class is useful when its type parameter F[_] has a
 * structure that can be combined for any particular type. Thus,
 * SemigroupK is like a Semigroup for kinds (i.e. parameterized
 * types).

function as first-order values

I think there's a misunderstanding of the terms. The oft repeated analogy, "kind is to a type, as type is to a value" probably isn't going to clarify it either, but it's a start. Consider the following:

scala> (_: Int) + 1
res0: Int => Int = <function1>

In fp, we can consider functions to be a value, and in Scala, we can store it in a variable:

scala> val f = (_: Int) + 1
f: Int => Int = <function1>

If we pass in some Int, we can derive a proper value e.g. 2. Because Int => Int is one order away from the proper value, it's also called a first-order value. (A function that accepts Int => Int and returns Int would be a higher-order value, but it doesn't matter here) The important point is that f is a value, not a type.

type constructor as first-order types

Next, let's consider the type equivalent of the Int => Int, which is Option:

scala> :k -v Option
scala.Option's kind is F[+A]
* -(+)-> *
This is a type constructor: a 1st-order-kinded type.

Option accepts a single parameter A to become a proper type. Just as we considered f to be a value, we consider Option to be a type. It's just first-order kinded.
Parameterized types can be called "type constructors" or "type functions", but they themselves are not "kinds."

Semigroup which operates on types

A semigroup that operates on types would be something like a type constructor =>[_, _], since you can take type A and type B and construct A => B.

Semigroup which operates on kinds

Using the standard notation, the values for kinds are combination of *, -> and parenthesis. So, the semigroup that operates on kinds would be something along the lines of _ -> _, where you pass in kind A and kind B and construct A -> B. This is clearly not what SemigroupK is doing.

SemigroupF?

I'm not sure what a good alternative would be but I hope I was able to demonstrate that neither "type level" nor "kind level" is appropriate. Maybe we can call it SemigroupF for type constructors that take a single operator.

[jbgi]

SemigroupU? (Universally quantified)

[non]

I think you're right that the documentation is poorly-worded. As you point out, SemigroupK doesn't operate on types, but on type constructors which can be parameterized on any type. I think we could definitely clear up the wording there.

I'm not convinced that an "F" suffix is any more meaningful than a "K" suffix. I'll have to sleep on it. But thanks for bringing this up!

[kailuowang]

I have always thought of "K" in SemigroupK and other "K" type classes as an indicator that these type classes operate on higher kinded types than their non "K" counterparts. So I feel that the scaladoc misleads, the "K" in the name does not.

[eed3si9n]

@kailuowang Option is F[+A] in Scala notation, * -(+)-> * in the standard notation, which is a type constructor that accepts a proper type. This is a first-order-kinded type.

A higher-kinded type would something that accepts F[A] as a type parameter like cats.Functor:

scala> import cats.Functor
import cats.Functor

scala> :k -v Functor
cats.Functor's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

[kailuowang]

@eed3si9n thanks for the clarification. I wasn't thinking of the specific "higher-kinded type" when I say "higher kinded" (although it definitely looks that way) , I was thinking a kind with higher order, like Option is "higher" than Int. I was thinking first-order-kinded is "higher" than direct-order kind, but now that I just said it, it's more like "further" than "higher"?

[eed3si9n]

@kailuowang Right, but that's like calling higher-order function (a function that accepts a function) as typelevel Semigroup, or SemigroupT.

@non:

As you point out, SemigroupK doesn't operate on types, but on type constructors which can be parameterized on any type.

I think SemigroupK operates on values x and y, not proper types or type constructors (first-order kinded types):

def combineK[A](x: F[A], y: F[A]): F[A]

[milessabin]

I remember having a conversation with @non about this some time back ...

I also didn't particularly like K as a suffix, because I didn't think that the association with "Kind" was particularly helpful. I remember mumbling that maybe there was a connection with parametricity, ie. the distinction between the monoid for List[Int] vs. the monoid for List was that the latter was parametric in the element type whereas the former wasn't. That might give us a P suffix instead of K.

I don't remember how the conversation continued from there ... clearly we didn't do anything about it :-)

[milessabin]

Another option might be to use a 1 suffix ... that's a convention we've adopted elsewhere.

[eed3si9n]

To be fair, there is some lifting going on here that's parametric and cool. But the level of lifting that's happening here is similar to that of Applicative:

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

We can think of it as a special case where a, b, and c are the same; the resulting signature becomes f a -> f a -> fa. In category theory, I think there's a name for this notion of arrow between category C and D: A functor, or endofunctor for the case of C to C. Thus to me, SemigroupF kind of makes sense. What's the problem :)

[milessabin]

I think the "endo" part is key here ... it has to be endo because we (need to) know nothing about the element types, so identity is our only choice. So I think that F for functor would imply more generality than there really is here.