Why does Scala allow nested data structures like List or Array

Question

Why does a language like Scala, with a very strong static type system, allow the following constructions:

 scala> List(1, List(1,2))
 res0: List[Any] = List(1, List(1, 2))

The same thing works if you replace List with Array. I learned functional programming in OCaml, which would reject the same code at compile-time:

# [1; [1;2]; 3];;
Characters 4-9:
  [1; [1;2]; 3];;
      ^^^^^
Error: This expression has type 'a list
       but an expression was expected of type int

So why does Scala allow this to compile?

Answer 1

tl;dr

Long story short, OCaml and Scala use two different classes of type systems: the former has structural typing, the latter has nominal typing, so they behave differently when it comes to type inference algorithms.

---

Full discussion

If you allow nominal subtyping in your type system, that's pretty much what you get.

When analyzing the List, the Scala compiler computes the type as the LUB (least upper bound) of all types that the list contains. In this case, the LUB of Int and List is Any. Other cases would have a more sensible result:

@ List(Some(1), None)
res0: List[Option[Int]] = List(Some(1), None)

The LUB of Some[Int] and None is Option[Int], which is usually what you expect. It would be "weird" for the user if this failed with:

expected List[Some[Int]] but got List[Option[Int]]

OCaml uses structural subtyping, so its type system works differently when it comes to type inference. As @gsg pointed out in the comments, OCaml specifically doesn't unify the types like Scala, but requires an explicit upcast.

In Scala, the compiler unifies the types when performing type inference (due to nominal subtyping.)

Of course you can get much better errors with explicit type annotations:

@ val x: List[Int] = List(1, List(1, 2))
Compilation Failed
Main.scala:53: type mismatch;
 found   : List[Any]
 required: List[Int]
}.apply
  ^

You can get warnings whenever the compiler infers Any - which is usually a bad sign - using the -Ywarn-infer-any flag. Here's an example with the scala REPL:

scala -Ywarn-infer-any
Welcome to Scala version 2.11.7 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_51).
Type in expressions to have them evaluated.
Type :help for more information.

scala> List(1, List(1, 2))
<console>:11: warning: a type was inferred to be `Any`; this may indicate a programming error.
       List(1, List(1, 2))
            ^
res0: List[Any] = List(1, List(1, 2))

Answer 2

Since Scala allows implicit subtyping, it is able to infer the "correct" type for such expressions with mixed contents. Scala correctly infers that your list is of type List[Any], meaning anything can occur within it.

Since Ocaml does not support implicit subtyping without explicit downcast; it is not able to automatically widen the type for mixed lists.

Most often, if you end up with type Any or AnyRef, you have messed something, but it can also be the right thing in some situations. It is up to the programmer to decide whether a more stringent type is required.