I was very surprised, having only started Scala recently, that it cannot infer types in function arguments. OCaml has no problems with this.

Scala doesn't have Hindley-Milner global type inference (of which OCaml has an extended version of) and instead uses a form of local type inference. Hindley-Milner doesn't work well (i.e. undecidable) in the face of overloading and inheritance.

If I understand "type erasure" correctly, Haskell and ML both do have type erasure.

In Haskell, using typeclasses like Typeable, you get the power of keeping types in runtime, but the types are actually erased.

Oh, sure. Sometimes types disappear at compile-time and aren't needed during program execution: the theorem is already proven so why should the runtime system carry around the baggage? Unless we're talking past one another, the Scala problem is rather worse: start passing around Seq[Seq[Int]]'s through your code and the compiler will be unable to ensure that it's always a Seq[Int] stuffed in there; the compiler comes with warning flags, but it's rather a bother and decidedly more dynamic.

You are quite correct, almost all strongly typed languages perform some type erasure for efficiency purposes. The problem, as I see it with Scala, is rooted in defect in the JVM; the system looses type information and cannot verify at compile-time that all your types will be correct.

Please correct me if I'm wrong or have misunderstood you.

I don't know Scala -- but it sounds like a compile-time type-verification problem more than a type erasure problem.

When Haskell targets x86, the x86 opcodes surely don't help Haskell verify that [[Int]] really has [Int]s in there, but it's not necessary because it is proven at compile-time. So I am a bit confused why Scala needs the JVM's help.

Consider that Haskell does its compilation step once; the types and their parameters are discarded and machine code is generated up front. (More correctly, LLVM IR is generated and combined with the Run Time System into a binary.) In Scala, and Java before it, compilation happens during program execution: you cannot discard types because the compilation step is never over. Ordersky's previous work on Pizza ensured that, however, that type parameters _were_ lost; rather than modify the JVM to support generics it proved to be more expedient with regard to backward compatibility just to strip them out. Pre-generics binary code could co-exist with post-generics because they compiled down to the same bytecode. Hence the complaint that in Java Array[Int] and Array[String] generates two special purpose, 'parameterized' Array structures in memory. Mostly the Java compiler can be clever and produce relatively only what is needed during execution, but the PermGem exception happens because, well, it's a hack.

Now, consider the difficulty of Scala wherein it's possible to represent a compound type. Erasure ensures that only the first parameter in the chain is generated in the type-erasure step, destroying the meaning of the union. There are kludgy ways around this--wrapping, bundling up manifests--but in the end the JVM does not allow the transmission of necessary information efficiently. Manifests serve the purpose of maintaining parameter information at runtime, but do so at the expense of code cache space and stress system resources. PermGem exceptions are much more common, in my experience, when doing Scala work as compared to Java.

The shorter answer to your question is the JIT nature of Java combined with a byte-code designed not to maintain the information needed to generate all possibilities of machine code on demand. LLVM IR maintains such information for Haskell--when targeting machine code directly I believe this is achieved by static polymorphic compilation, but I could be wrong; Stack Overflow time?--and the CLR does the same for C# and friends. It's a JVM problem entirely. The JVM promises to perform any and all compilation but is unable to accept all the information needed to do so effectively.