CODEWITHSUNDEEP
scalacompilationcompiler-errorsfunctional-programming
Rafa Paez
Rafa Paez

Reputation: 4860

Scala type checking compilation error

I have the following functions

  def map[A,B](l: List[A])(f: A => B): List[B]

  def concat[A](l: List[List[A]]): List[A]

I wanted to implement this one 

  def flatMap[A,B](l: List[A])(f: A => List[B]): List[B]

Now, I know that a correct solution is (so this is not the question)

  def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] = 
    concat(map(l)(f))

But when I was trying to resolve it, I first tried with (I forgot to concat)

  def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] = 
    map(l)(f)

// compilation output
[error]  found   : A => fpinscala.datastructures.List[B]
[error]  required: A => B
[error]     map(l)(f)

I cannot understand that error, because looks like the evaluation of the map(l)(f) is wrong, but it is not, it is the returned value of the flatMap function what is wrong.

In fact, if a decompose the same implementation in two lines of code, we can see that the Scala compiler complains about another different error - actually is the error that I expected also in the previous code.

  def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] = {
    var result = map(l)(f)
    result
  }

// compilation output
[error]  found   : fpinscala.datastructures.List[fpinscala.datastructures.List[B]]
[error]  required: fpinscala.datastructures.List[B]
[error]     result

Could anyone explain me why the compilation of the first try of code is given a different kind of error that the second one?

Upvotes: 2

Views: 404

Answers (1)

hivert
hivert

Reputation: 10667

You have to know how Scala check types. It is using an Unification algorithm. In simple words it means that it follows a top/down approach.

Recall that map is of type List[U] => (U => V) => List[V] (whatever type U and V are). In the first wrong code, you wrote that your function returns a List[B]. Therefore you tell Scala that map(l)(f) must be of type List[B]. Now you propagate the constains in a top/down way. For map(l)(f) to be of type List[B], you need to have l of type List[A] (whatever A is) and f of type A => B. Thus the compiler is complaining because you gave f of type A => list[B].

If the second wrong code, you already correctly computed result of type List[List[B]]. However, in the second line you try to return result but your function is declared to return a list[B]. Hence the error message.

Upvotes: 5

Related Questions