alifirat alifirat - 10 months ago 48
Scala Question

Why does Scala allow nested data structures like List or Array

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
. 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 Source


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]

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))