Why is Scala's type inference not as powerful as Haskell's?

Question

The type inference engine of Haskell is much more powerful than Scala's. In Haskell I rarely have to explicitly write the types whereas in Scala the types can only be inferred in expressions but not in method definitions.

For example, see following Haskell code snippet:

size xs = loop xs 0   where     loop [] acc = acc     loop (_ : xs) acc = loop xs (acc+1) 

It returns the size of a List. The Haskell compiler can recognize what types are used and what the function definition is. The equivalent Scala code:

def size[A]: List[A] => Int = xs => {   def loop: (List[A], Int) => Int = {     case (Nil, acc) => acc     case (_ :: xs, acc) => loop(xs, acc+1)   }   loop(xs, 0) } 

Or with method definitions:

def size[A](xs: List[A]) = {   def loop(xs: List[A], acc: Int): Int = xs match {     case Nil => acc     case _ :: xs => loop(xs, acc+1)   }   loop(xs, 0) } 

My question is: Why can't I write them like the following?

def size = xs => {   def loop = {     case (Nil, acc) => acc     case (_ :: xs, acc) => loop(xs, acc+1)   }   loop(xs, 0) } 

Once again with method definitions:

def size(xs) = {   def loop(xs, acc) = xs match {     case Nil => acc     case _ :: xs => loop(xs, acc+1)   }   loop(xs, 0) } 

Is it because nobody has implemented it yet? Is the type system of Scala not as powerful as needed for this case? Or are there other reasons?

Answer 1

The main reason is that the type system of Scala allows sub-typing, which the Hindley-Milner type inference algorithm does not support.

Haskell does not have sub-typing, so the algorithm works much better there, although many popular type system extensions supported by GHC cause type inference to fail again, forcing you to provide explicit type signatures for some expressions.

In the end, it's a trade-off between the power of the type system and the amount of type inference that can be done. Scala and Haskell have simply made different trade-offs.