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?

possible duplicate of Disadvantages of Scala type system versus Haskell? — Kevin Wright
@missingfaktor - Inference is just a subset of the type system as a whole, but "duplicate" is the closest way that SO has to expressing this relationship. — Kevin Wright

hammar hammar · Accepted Answer · 2011-08-29T18:27:44

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.

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

4 Answers