Maulik Soneji Maulik Soneji - 13 days ago 7
Scala Question

Parameterised Class vs Function

I had a query about what is the difference between parameterising the class vs parameterising the function.

I have provided implementation of a Functor as follows:

trait Functor[F[_],A,B] {
def map(fa: F[A]) (f: A => B) : F[B]
}


and the other where the function is parameterised as follows:

trait Functor[F[_]] {
def map[A,B](fa: F[A]) (f: A => B) : F[B]
}


Where are the cases where we should use one over another?

Another follow up question:
Why do we pass the argument to functor as F[_] and not as F[A] or F[B]. What cases arise when we use either F[A] or F[B]?

Answer

Always prefer the second one. With the first one you can implement instances as nonsensical as:

trait WrongFunctor[F[_],A,B] {
  def map(fa: F[A])(f: A => B) : F[B]
}

case class notEvenRemotelyAFunctor[A]() extends WrongFunctor[List,A,Int] {

  def map(fa: List[A])(f: A => Int) : List[Int] = 
    if(f(fa.head) < 4) List(3) else List(4)
}

type Id[X] = X
case object ILikeThree extends WrongFunctor[Id, Int, Int] {

  def map(fa: Int)(f: Int => Int): Int = if(fa == 3) 3 else f(fa)
}

Even if you do things right, you'd need for a fixed functor implementation one object per different types at which you want to use fmap. But the important point is that the second one at least makes it harder to write that kind of wrong "functors"; less non-functors will slip by:

trait Functor[F[_]] {

  def map[A,B](fa: F[A])(f: A => B) : F[B]
}
case object ILikeThreeAgain extends Functor[Id] {

  def map[A,B](fa: A)(f: A => B) : B =
    ??? // how do I write the above here?
}

The keywords here are parametricity and parametric polymorphism. The intuition is that if something is defined generically, you can derive properties it will satisfy just from the types involved. See for example Bartosz Milewski blog - Parametricity: Money for Nothing and Theorems for Free for a good explanation, or the canonical Theorems for free paper.

Follow-up question

Another follow up question: Why do we pass the argument to functor as F[_] and not as F[A] or F[B]. What cases arise when we use either F[A] or F[B]?

Because that's part of what a functor is; it is a "constructor":

  1. for each input type A it gives you as output another type F[A]
  2. and for each function f: A => B, another function fmap(f): F[A] => F[B] satisfying fmap(id[A]) == id[F[A]] and fmap(f andThen g) == fmap(f) andThen fmap(g)

So for 1. you need a way of representing functions on types; and that's what F[_] is.

Note that having a map method like in your signature is in this case equivalent to fmap:

trait Functor[F[_]] {

  def map[A,B](fa: F[A])(f: A => B) : F[B]

  def fmap[A,B](f: A => B): F[A] => F[B] =
    { fa => map(fa)(f) }

  def mapAgain[A,B](fa: F[A])(f: A => B) : F[B] =
    fmap(f)(fa)
}

Now for how this links with real category theory:

Instances of your Functor[F[_]] trait above are meant to represent Scala-enriched functors

F: ScalaScala

Let's unpack this.

There's a (usually implicitly defined) category Scala with objects types, and morphisms functions f: A ⇒ B. This category is cartesian closed, where the internal hom is the type A ⇒ B, and the product (A,B). We can work then with Scala-enriched categories and functors. What's a Scala-enriched category? basically one that you can define using Scala the language: you have

  1. a set of objects (which you'd need to represent as types)
  2. for each A,B a type C[A,B] with identities id[X]: C[X,Y] and composition andThen[X,Y,Z]: (C[X,Y], C[Y,Z]) => C[X,Z] satisfying the category axioms

Enriched functors F: C → D are then

  1. a function from the objects of C to those of D, A -> F[A]
  2. for each pair of objects A,B: C a morphism in Scala i.e. a function fmap: C[A,B] => C[F[A], F[B]] satisfying the functor laws fmap(id[A]) == id[F[A]] and fmap(f andThen g) == fmap(f) andThen fmap(g)

Scala is naturally enriched in itself, with Scala[X,Y] = X => Y, and enriched functors F: ScalaScala are what instances of your Functor[F[_]] trait are meant to represent.

Of course this needs all sort of qualifications about how Scala breaks this and that, morphism equality etc. But the moral of the story is: your base language L (like Scala in this case) is likely trying to be a cartesian-closed (or at least symmetric monoidal-closed) category, and functors definable through it correspond to L-enriched functors.

Comments