Failure parsing views

Question

I define the following diff function on Seq[Int] which uses view to avoid copying data:

object viewDiff {
  def main(args: Array[String]){
    val values = 1 to 10
    println("diff="+diffInt(values).toList)
  }

  def diffInt(seq: Seq[Int]): Seq[Int] = {
    val v1 = seq.view(0,seq.size-1)
    val v2 = seq.view(1,seq.size)
    (v2,v1).zipped.map(_-_)
  }
} 

This code fails with an UnsupportedOperationException. If I uses slice instead of view it works.

Can anyone explain this?

[tested with scala 2.10.5 and 2.11.6]

Edit

I selected Carlos's answer because it was the (first) correct explanation of the problem. However, som-snytt's answer is more detailed, and provides a simple solution using view on the zipped object.

I also posted a very simple solution that works for this specific case.

Note

In the code above, I also made a mistake on the algorithm to compute a seq derivative. The last line should be: seq.head +: (v2,v1).zipped.map( _-_ )

Litta

Answer 1

When you use seq.view in your code, you are creating SeqView[Int, Seq[Int]] objects that cannot be zipped, as it can't support TraversableView.Builder.result. But you can use something like this:

def diffInt(seq: Seq[Int]) = {
  val v1 = seq.view(0,seq.size-1)
  val v2 = seq.view(1,seq.size)

  (v2.toList,v1.toList).zipped.map {
    case (x1: Int, y1: Int) => x1-y1
    case _ => 0
  }
}

Tass

This is indeed the problem (view + zipped) but: shouldn't compilation fail then? – Litta

Also, your solution fails with the same exception too – Litta

I didn't add the part that makes it work. I have transformed the views into lists so we have a Traversable object for the zipped. – Tass

Forcing the views in creating intermediate lists is the wrong approach. – Giles

Answer 2

That looks strange indeed, and the zipped seem to be the culprit. What you can do instead, as a minimal change, is to use zip:

def diffInt(seq: Seq[Int]): Seq[Int] = {
  val v1 = seq.view(0,seq.size-1)
  val v2 = seq.view(1,seq.size)
  v2.zip(v1).map { case (x1, x2) => x1 - x2 }
}

Turtle

but zip will copy the values (I think?) and make lots of tuple boxing, which I try to avoid... – Litta

I also thought about zip copying the elements. See my other answer for an alternative approach. – Turtle

Answer 3

Normally, you don't build views when mapping them, since you want to defer building the result collection until you force the view.

Since Tuple2Zipped is not a view, on map it tries to build a result that is the same type as its first tupled collection, which is a view.

SeqView's CanBuildFrom yields the NoBuilder that refuses to be forced.

Since the point of using Tuple2Zipped is to avoid intermediate collections, you also want to avoid forcing prematurely, so take a view before mapping:

scala> Seq(1,2,3).view(1,3)
res0: scala.collection.SeqView[Int,Seq[Int]] = SeqViewS(...)

scala> Seq(1,2,3).view(0,2)
res1: scala.collection.SeqView[Int,Seq[Int]] = SeqViewS(...)

scala> (res0, res1).zipped
res2: scala.runtime.Tuple2Zipped[Int,scala.collection.SeqView[Int,Seq[Int]],Int,scala.collection.SeqView[Int,Seq[Int]]] = (SeqViewS(...), SeqViewS(...)).zipped

scala> res2.view map { case (i: Int, j: Int) => i - j }
res3: scala.collection.TraversableView[Int,Traversable[_]] = TraversableViewM(...)

scala> .force
res4: Traversable[Int] = List(1, 1)

Here's a look at the mechanism:

import collection.generic.CanBuildFrom
import collection.SeqView
import collection.mutable.ListBuffer
import language._

object Test extends App {
  implicit val cbf = new CanBuildFrom[SeqView[Int, Seq[Int]], Int, Seq[Int]] {
    def apply(): scala.collection.mutable.Builder[Int,Seq[Int]] = ListBuffer.empty[Int]
    def apply(from: scala.collection.SeqView[Int,Seq[Int]]): scala.collection.mutable.Builder[Int,Seq[Int]] = apply()
  }

  //val res = (6 to 10 view, 1 to 5 view).zipped.map[Int, List[Int]](_ - _)
  val res = (6 to 10 view, 1 to 5 view).zipped.map(_ - _)
  Console println res
}

Giles

Answer 4

Ah, those good old times of imperative programming:

val seq = 1 to 10
val i1 = seq.iterator
val i2 = seq.iterator.drop(1)
val i = scala.collection.mutable.ArrayBuffer.empty[Int]
while (i1.hasNext && i2.hasNext) i += i2.next - i1.next
println(i)

I'd say it's as efficient as it gets (no copying and excessive allocations), and pretty readable.

Turtle

I tried something like that but the efficiency was better only for very large seq, and not that much. I could try this code to be sure but,... I think I'll stay with my answer – Litta

Answer 5

As Carlos Vilchez wrote, zipped cannot work with view. Looks like a bug to me...

But this only happens if the first zipped seq is a view. As the zipped is stopping when any of its seq is finished, it is possible to use the whole input seq as first zipped item and inverse the - operation:

def diffInt2(seq: Seq[Int]): Seq[Int] = {
  val v1 = seq//.view(0,seq.size-1)
  val v2 = seq.view(1,seq.size)
  seq.head +: (v1,v2).zipped.map( (a,b) => b-a )  // inverse v1 and v2 order
}

Litta