CODEWITHSUNDEEP
scalalistdictionarycollectionstuples
PawkyPenguin
PawkyPenguin

Reputation: 250

Scala: map and unzip list in one pass

I have a list of tuples as follows:

[(8, 3, 9), (10, 3, 0), (-37, 4, 1)]

I would like to map this list and simultaneously unzip it in one pass. Here is an example with two passes (or at least I strongly assume it takes two passes, if not then we're done here :D)

val l = List((8, 3, 9), (10, 3, 0), (-37, 4, 1))
val (list1, list2) = l.map({ el => (el._1, el._2) }).unzip

Of course I could just do this in an imperative style by looping over the lists and appending to a collection but is there a way to do this in a succinct functional way? I'm guessing I would essentially need a lazy map followed by an eager unzip.

Upvotes: 1

Views: 1246

Answers (3)

mgd
mgd

Reputation: 4332

Use unzip with a function

In Scala, the unzip operation takes as an implicit parameter a function to produce the pair so you can map and unzip in one go. Here is how it looks in Scala 2.13.4 docs for List:

def unzip[A1, A2](implicit asPair: (A) => (A1, A2)): (List[A1], List[A2])

By passing your own asPair function, you can accomplish the result you are looking for:

scala> val l = List((8, 3, 9), (10, 3, 0), (-37, 4, 1))
val l: List[(Int, Int, Int)] = List((8,3,9), (10,3,0), (-37,4,1))

scala> val (list1, list2) = l.unzip(el => (el._1, el._2))
val list1: List[Int] = List(8, 10, -37)
val list2: List[Int] = List(3, 3, 4)

Algorithmic Complexity

The source code for the unzip function lives in trait scala.collection.IterableOps in file Iterable.scala:

def unzip[A1, A2](implicit asPair: A => (A1, A2)): (CC[A1], CC[A2]) = {
  val first: View[A1] = new View.Map[A, A1](this, asPair(_)._1)
  val second: View[A2] = new View.Map[A, A2](this, asPair(_)._2)
  (iterableFactory.from(first), iterableFactory.from(second))
}

If I read it correctly, the list is actually traversed twice: once for each list produced.

However, in your original solution, the list was traversed three times: once for the map operation and twice for the unzip operation so my solution is still an improvement.

The solution using foldRight suggested by @jwvh seems to only traverse the list once but foldRight has an overhead of initially reversing the list (in order to take from the head of the list). So I guess my solution has exactly the same algorithmic complexity. (Please correct me if I am wrong.)

Upvotes: 1

Richard Sitze
Richard Sitze

Reputation: 8463

This is very specific to your stated problem; it doesn't solve a more general problem. Try:

val (list1, list2, _) = l.unzip3

Edit

To be fair, after locating the implementation scala.collection.generic.GenericTraversableTemplate.unzip3, it's a very non-functional loop that builds 3 lists and returns them, pretty much as described in the original question. At least it's one-pass and not just burying the two-pass.

Upvotes: 3

jwvh
jwvh

Reputation: 51271

There's always fold.

val (list1, list2) = l.foldRight((List.empty[Int],List.empty[Int])){
  case ((a,b,_),(l1,l2)) => (a::l1,b::l2)
}

Upvotes: 2

Related Questions