Shuffling Range in Scala is Odd

Question

Check out this REPL session (I've tidied it up for readability):

scala> val x = 1 to 10
x: Range.Inclusive = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val y = x.toSeq
y: Range = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> x eq y
res14: Boolean = true

scala> util.Random.shuffle(y)
<console>:10: error: Cannot construct a collection of type scala.collection.AbstractSeq[Int] with elements of type Int based on a collection of type scala.collection.AbstractSeq[Int].
              util.Random.shuffle(y)
                                 ^

scala> util.Random.shuffle(x)
res16: scala.collection.immutable.IndexedSeq[Int] = Vector(8, 3, 4, 2, 10, 9, 7, 5, 6, 1)

First, this should work regardless of the fact that the types are different. The question is 'Why?'

psp · Answer 1 · 2015-05-09T01:07:55.877

5

It's SI-6948, a bug caused by fundamental scala brokenness.

Here's a nice long commit message with some additional explanation.

edited May 09 '15 at 01:07

answered May 09 '15 at 00:57

psp

12,138
1
41
51

https://gitter.im/scala/scala?at=554d5ab5675c1d50549ec0f1 is arguably typographically more expressive. – som-snytt May 09 '15 at 19:10

som-snytt · Answer 2 · 2015-05-09T00:06:10.817

For some reason, type inference for the shuffle produces a different result for an Inclusive as opposed to a Range.

The reason toSeq results in Range is that its definition innocently narrows the type:

override def toSeq = this

There is an open issue to infer the result type of the overridden method instead.

Showing that the REPL isn't lying:

scala> import util.Random.shuffle
import util.Random.shuffle

scala> val x = 1 to 10
x: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val y = x.toSeq
y: scala.collection.immutable.Range = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val z: Range = x
z: Range = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> shuffle(x)
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 5, 2, 10, 9, 6, 3, 7, 4, 8)

scala> shuffle(y)
<console>:11: error: Cannot construct a collection of type scala.collection.AbstractSeq[Int] with elements of type Int based on a collection of type scala.collection.AbstractSeq[Int].
              shuffle(y)
                     ^

Snipping to see what was inferred and what implicit was used:

scala> :replay -Xprint:typer

Replaying: shuffle(x)
        private[this] val res0: scala.collection.immutable.IndexedSeq[Int] = scala.util.Random.shuffle[Int, scala.collection.immutable.IndexedSeq]($line5.$read.$iw.$iw.x)(immutable.this.IndexedSeq.canBuildFrom[Int]);

scala> shuffle(y)
        private[this] val <res1: error>: <error> = scala.util.Random.shuffle[Int, scala.collection.AbstractSeq]($line6.$read.$iw.$iw.y)();

instead of what you hoped:

scala> shuffle[Int, collection.immutable.IndexedSeq](z)
res3: scala.collection.immutable.IndexedSeq[Int] = Vector(6, 5, 3, 8, 4, 1, 2, 10, 7, 9)

With -Ytyper-debug, there's an extra type param A that seems to let it proceed for Inclusive, but I don't know offhand where that comes from.

|    |    |    |    |-- x BYVALmode-EXPRmode-POLYmode (site: value res3  in $iw) 
|    |    |    |    |    \-> scala.collection.immutable.Range.Inclusive
|    |    |    |    solving for (T: ?T, CC: ?CC)
|    |    |    |    solving for (A: ?A)
|    |    |    |    [adapt] [A]=> scala.collection.generic.CanBuildFrom[scala.collect... adapted to [A]=> scala.collection.generic.CanBuildFrom[scala.collect... based on pt scala.collection.generic.CanBuildFrom[scala.collection.immutable.IndexedSeq[Int],Int,scala.collection.immutable.IndexedSeq[Int]]
|    |    |    |    |-- [T, CC[X] <: TraversableOnce[X]](xs: CC[T])(implicit bf: ... EXPRmode (site: value res3  in $iw) 
|    |    |    |    |    \-> scala.collection.immutable.IndexedSeq[Int]
|    |    |    |    [adapt] [T, CC[X] <: TraversableOnce[X]](xs: CC[T])(implicit bf: ... adapted to [T, CC[X] <: TraversableOnce[X]](xs: CC[T])(implicit bf: ...
|    |    |    |    \-> scala.collection.immutable.IndexedSeq[Int]

Is it a bug or a behavior?

Making it plain:

scala> import language.higherKinds, collection.TraversableOnce, collection.generic.CanBuildFrom
import language.higherKinds
import collection.TraversableOnce
import collection.generic.CanBuildFrom

scala> def f[T, CC[X] <: TraversableOnce[X]](xs: CC[T])(implicit cbf: CanBuildFrom[CC[T],T,CC[T]]): CC[T] = null.asInstanceOf[CC[T]]
f: [T, CC[X] <: scala.collection.TraversableOnce[X]](xs: CC[T])(implicit cbf: scala.collection.generic.CanBuildFrom[CC[T],T,CC[T]])CC[T]

scala> f(1 to 10)
res0: scala.collection.immutable.IndexedSeq[Int] = null

scala> f(1 until 10)
<console>:12: error: Cannot construct a collection of type scala.collection.AbstractSeq[Int] with elements of type Int based on a collection of type scala.collection.AbstractSeq[Int].
              f(1 until 10)
               ^

Shuffling Range in Scala is Odd

2 Answers2