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

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
开发者_如何学Python    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?

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.

I guess the main reasons have already been given, but I find this quote by Scala's creator Martin Odersky to be particularly informative,

The reason Scala does not have Hindley/Milner type inference is that it is very difficult to combine with features such as overloading (the ad-hoc variant, not type classes), record selection, and subtyping. I’m not saying impossible — there exist a number of extensions that incorporate these features; in fact I have been guitly of some of them myself. I’m just saying it’s very difficult to make this work well in practice, where one needs to have small type expressions, and good error messages. It’s not a shut case either — many researchers are working on pushing the boundaries here (look for instance at Remy’s MLF). But right now it is a tradeoff of better type inferencing vs better support for these features. You can make the tradeoff both ways. The fact that we wanted to integrate with Java tipped the scales in favor of subtyping and away from Hindley/Milner.

Source: comment under post Universal Type Inference is a Bad Thing.

hammar gave the biggest reason. Here are two others:

• Scala uses types to resolve names

Consider

def foo(x) = x.a + x.b

How could Scala possibly infer the type of the argument? Should it look for every class with an a and b field? What if there are more than 1? In Haskell

foo x = (a x) + (b x)

record names are unique, which presents its own problems, but means you can always infer what kind of record is being referred to.

• For your example: case expressions in Scala can be heterogeneous

In Scala the type of the object being matched can be used either as part of the match, or to decide how matching should be done. So even if all the constructors in the case are for List, you might want to pass something other than a list to it, and have it fail.

Another thing that doesn't play well with Hindley-Milner type inference is method overloading, and related features like default arguments and varargs. That's the reason why it is so hard to write things like zipWithN in Haskell (which is trivial in Scala).

I have read some responses above, however some of such conclusions may be set in doubt when you realize that F# embraces full sub-typing with OOP within Hindley-Milner type inference since 2006.

4. Addition of method overload resolution and object-expressions for interoperability with .NET (2004)

6. Addition of class/interface constructs for object programming (2005)

5. Addition of “statically resolved type parameters” for handling overloaded arithmetic in a way that fits with Hindley-Milner type inference (2005)

9. Addition of a treatment of subtyping within Hindley-Milner type inference (2006)

Source history of F#