2.12 Type System Bug "A = List[A]" ...?

92 views
Skip to first unread message

Sylvia Grewe

unread,
Nov 8, 2016, 1:07:59 PM11/8/16
to scala-internals
The following behavior of Scala 2.12 seems undesired:

def flatten[A](xss: List[A]): List[A] = xss match {
    case Nil => Nil
    case (head:List[A])::tail => flatten(head):::flatten(tail)
    case (head:A)::tail => head::flatten(tail)
  }

<console>:13: warning: abstract type A in type pattern List[A] (the underlying of List[A]) is unchecked since it is eliminated by erasure
           case (head:List[A])::tail => flatten(head):::flatten(tail)
                      ^
<console>:14: warning: abstract type pattern A is unchecked since it is eliminated by erasure
           case (head:A)::tail => head::flatten(tail)

scala> flatten(List(List(1), List(2,3,4), List(5,6)))
res1: List[List[Int]] = List(1, 2, 3, 4, 5, 6) //Wrong type?!

Scala 2.11.8 also compiles it (without any warning) and produces a ClassCastException when run.
Intuitively, I would say, flatten should not compile at all like this....



Adriaan Moors

unread,
Nov 8, 2016, 8:23:02 PM11/8/16
to scala-internals
Hi,

Type patterns are basically casts, and we let you write unsound versions of either (to varying degrees). We err on the side of flexibility here because you sometimes do need an escape hatch for the type checker :-)

Here, specifically, the unchecked warning reminds you that we cannot check the actual types passed to type parameters, since that information is erased at compile time. You may still know that at run time it will always have the expected type.

Cheers
Adriaan

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Sylvia Grewe

unread,
Nov 9, 2016, 4:27:08 AM11/9/16
to scala-internals
Ok, that is good to know. However, it still should not be possible to do stuff like this, right?

Welcome to Scala 2.12.0 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_31).
Type in expressions for evaluation. Or try :help.

scala> def flatten[A](xss: List[A]): List[A] = xss match {
     |     case Nil => Nil
     |     case (head:List[A])::tail => flatten(head):::flatten(tail)
     |     case (head:A)::tail => head::flatten(tail)
     |   }
<console>:13: warning: abstract type A in type pattern List[A] (the underlying of List[A]) is unchecked since it is eliminated by erasure
           case (head:List[A])::tail => flatten(head):::flatten(tail)
                      ^
<console>:14: warning: abstract type pattern A is unchecked since it is eliminated by erasure
           case (head:A)::tail => head::flatten(tail)
                      ^
flatten: [A](xss: List[A])List[A]

scala> flatten(List(List(1), List(2,3,4), List(5,6)))
res0: List[List[Int]] = List(1, 2, 3, 4, 5, 6)

scala> flatten(List(List("1"), List("2","3","4"), List("5","6")))
res1: List[List[String]] = List(1, 2, 3, 4, 5, 6)

scala> res0:::List(List(1), List(2), List(3,4))
res4: List[List[Int]] = List(1, 2, 3, 4, 5, 6, List(1), List(2), List(3, 4))

I would expect this to fail immediately....

Roland Kuhn

unread,
Nov 9, 2016, 4:58:35 AM11/9/16
to scala-i...@googlegroups.com
Hi Sylvia,

the issue is that in the very signature of flatten() you are lying to the compiler: what you pass in is not a List[A]. The type of what you want to pass in (given your implementation) is not expressible in Scala, and as far as I know it is even inexpressible in dotty, at least if you want to allow arbitrary nesting; a finite approximation might be List[A | List[A | List[A]]].

You may try out writing “List(1, List(2, 3))” in the REPL and observe the type of this expression.

The fact that Scala allows you to do some operations that it cannot verify is very useful in certain cases, and if you do not want to use this possibility then you should heed the warnings.

Regards,

Roland

Sylvia Grewe

unread,
Nov 9, 2016, 6:33:38 AM11/9/16
to scala-internals
Thanks a lot for the clarifications, I learned a lot about type casts today ;).
Reply all
Reply to author
Forward
0 new messages