Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why Is Functor a Higher-Kinded type

I have following functor definition

trait Functor[F[_]] { 
    def map[A, B](fa: F[A])(f: A => B): F[B]
}
object ListFunctor extends Functor[List] { //
    def map[A, B](f: A => B)(data: List[A]): List[B] = data map f
}

In scala, it is very common that F is a collection type, such as List,Seq,Option, I would ask why Functor has to be higher kinded type, and what does the type parameter F really mean?

like image 881
Tom Avatar asked Aug 27 '17 05:08

Tom


People also ask

Why are there high Kinded types?

Higher-kinded types are useful when we want to create a container that can hold any type of items; we don't need a different type for each specific content type. As we already saw, Collection (in our previous example) allows various entity types.

What is higher Kinded types Haskell?

A higher kinded type is a concept that reifies a type constructor as an actual type. A type constructor can be thought of in these analogies: like a function in the type universe. as a type with a "hole" in it.

Does rust have higher Kinded types?

Rust does not have higher-kinded-types. For example, functor (and thus monad) cannot be written in Rust.


1 Answers

why Functor has to be higher kinded type

Functor has to be higher kinded because we want to abstract over a type parameter which itself takes a type parameter (we call this a type constructor, think Functor[List] as a concrete example).

The type of types that Functor deals with are called "first order kinds", their kind is of * -> *. When you looking at concrete instances for Functor, you see we dont provide the inner type parameter. For example, when you define a functor for List as you did in your example, you define it as a Functor[List]. We're not creating a functor for a proper type (i.e. List[Int]), but rather any type contained inside the List. This abstraction brings great power, because you can utilize it for any proper List type (of kind *), be it List[String], List[Int], etc..

I always like to refer to the image drawn by Adriaan Moore in his paper "Genrics Of A Higher Kind":

Higher Kinds

What does the type parameter F really mean

Fs sole purpose is to define a contract with the implementer of the Functor. By the signature of F we can deduce what kind of type Functor expects. When we see that it has one "placeholder" ([_]) we know, by convention, that this means that F should take a single type parameter. If we think about all the types that take a single type parameter, we can see that there are many, for example List, Option, Try, Future, Task, etc.

For a more broad explanation regarding higher kinded types, see What is a higher kinded type in Scala?

like image 93
Yuval Itzchakov Avatar answered Sep 20 '22 15:09

Yuval Itzchakov