Convert function that works with List[Int] to take Seq[Int]

Question

I've been provided with a solution on another question that works with List[Int] to get the indices at which two lists intersect.

@tailrec
def indicesOfIntersection(left: List[Int], right: List[Int], lidx: Int = 0, ridx: Int = 0, result: List[(Int, Int)] = Nil): List[(Int, Int)] = (left, right) match { 
    case (Nil, _) | (_, Nil) => result.reverse
    case (l::tail, r::_) if l < r => indicesOfIntersection(tail, right, lidx+1, ridx, result)
    case (l::_, r::tail) if l > r => indicesOfIntersection(left, tail, lidx, ridx+1,  result)
    case (l::ltail, r::rtail) => indicesOfIntersection(ltail, rtail, lidx+1, ridx+1, (lidx, ridx) :: result)
}

And am hoping to convert it to one that works directly on Arrays, without doing anything inefficient (because it is used on big arrays)

The advice I got was

Yeah Nil and head::tail extractors only work for lists. You can trivially rewrite it for any seq: just replace Nil with Seq() and head::tail with head+:tail

Unfortunately, the trivial is still over my head and I require a bit more spoon feeding :)

I took a stab with the following which passed compile-time checks, but fails at runtime:

@tailrec
def indicesOfIntersection(left: Seq[Int], right: Seq[Int], lidx: Int = 0, ridx: Int = 0, result: Seq[(Int, Int)] = Seq()): Seq[(Int, Int)] = (left, right) match { 
    case (l::tail, r::_) if l < r => indicesOfIntersection(tail, right, lidx+1, ridx, result)
    case (l::_, r::tail) if l > r => indicesOfIntersection(left, tail, lidx, ridx+1,  result)
    case (l::ltail, r::rtail) => indicesOfIntersection(ltail, rtail, lidx+1, ridx+1, (lidx, ridx) +: result)
    case (Seq(), _) | (_, Seq()) => result.reverse
}

scala.MatchError: (WrappedArray(19, 68, 419...

(error truncated due to essentially being a dump of my first array input)

Thanks in advance for pointing out what I've done wrong.

---

Update

I've gotten a little further by updating all instances of :: operators in the case statements to +: as well (although I don't understand the syntax, thinking this was just a place for destructuring).

It's running now, but I'm unsure if it's "correct" - specifically it seems that if the final case (formerly the first case) is comparing empty Seq() instances, they won't necessarily be considered equal just because the are both empty (unlike the former Nil comparison)?

---

Update

I've been informed in the comments that one cannot simply use tail on Arrays without incurring a heavy cost (presumably traversing the entire array?) so I'm still looking for a solution which replaces these nuances with something that is equally performant for Arrays (or any Seq, if you wish)

Answer 1

Try wrapping your Array using scala.collection.immutable.ArraySeq.unsafeWrapArray and then converting it to a View using .view.

Making it a View will allow you to take the tail without actually copying the underlying array.

See also https://docs.scala-lang.org/overviews/collections-2.13/views.html