ZipWithIndex for nested collections (stateless release)

There are several nested collections:

val xs = List(
           List("a","b"), 
           List("c"), 
           List("d", "e", "f"))

      

I want to create a unique index for nested list items:

val result = List(
         List(("a", 0), ("b", 1)), 
         List(("c", 2)),
         List(("d", 3), ("e", 4), ("f", 5)))

      

This is a bad solution (using mutable state):

val indexes:List[Int] = xs.flatten.zipWithIndex.map(_._2)
var idx = 0
val result = xs.map(_.map{ el =>
   val copy = (el, indexes(idx))
   idx = idx + 1
   copy
})

      

How can I release this stateless task?

+3


source to share


7 replies


Solution 1 (using fold

):

scala> xs.foldLeft((List[List[(String, Int)]](), 0)){ 
         case ((r, i), x) => (r:+x.zip(Stream.from(i)), i+x.size) 
       }._1
res1: List[List[(String, Int)]] = List(List((a,0), (b,1)), List((c,2)), List((d,3), (e,4), (f,5)))

      

Solution 2 (using recursion)



scala> def deepZip[A](ls: List[List[A]], i: Int = 0): List[List[(A, Int)]] = ls match {
     |   case Nil => Nil
     |   case x::xs => x.zip(Stream.from(i)) :: deepZip(xs, i+x.size)
     | }
deepZip: [A](ls: List[List[A]], i: Int)List[List[(A, Int)]]

scala> deepZip(xs)
res2: List[List[(String, Int)]] = List(List((a,0), (b,1)), List((c,2)), List((d,3), (e,4), (f,5)))

      

Solution 3:

scala> (xs, xs.map(_.size).scanLeft(0){ _+_ }).zipped map { (a, b) => a.zip(Stream.from(b)) }
res3: List[List[(String, Int)]] = List(List((a,0), (b,1)), List((c,2)), List((d,3), (e,4), (f,5)))

      

+3


source


Another variation:

val index = Iterator.from(0)
for (sl <- xs) yield for (e <- sl) yield (e, index.next)

      

Pretty neat IMO, but iterators are not purely functional of course



And functional, quite readable (for me, anyway)

 val starts = xs.scanLeft(0)(_ + _.size)
 (xs, starts, starts.tail).zipped map{ (sl, start, end) => sl zip ( start until end)}

      

+3


source


This is what I came up with:

def iterate(someList: List[List[Int]], counter: Int = 0, acc: List[List[(Int, Int)]] = List()): List[List[(Int, Int)]] = someList match {
  case head :: tail =>
    val newCounter = counter + head.length
    val sublist = head.zipWithIndex.map {
      // add the counter to the index
      case (v, i) => (v, i + counter)
    }
    // recurse
    iterate(tail, newCounter, acc :+ sublist)
  case _ => acc
}

scala> iterate(List(List(1,2), List(3,4)))
res3: List[List[(Int, Int)]] = List(List((1,0), (2,1)), List((3,2), (4,3)))

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

      

What it basically does is enumerate a list of lists, zip with the index of each sublist and add a counter value that takes into account all the previous lengths of the list, when the list is empty, we return the accumulator.

But as I said, I would not trade this with a modified version.

+2


source


You can always apply enough brute force to convert the required while loop to a functional one foldLeft

:

val xs = List(List("a", "b"), List("c"), List("d", "e", "f"))

def addIndeces(xs: List[List[String]]): List[List[(String, Int)]] = {
  val outerLoopState = 0 -> Vector.empty[List[(String, Int)]]

  val (finalCounter, finalResult) = xs.foldLeft(outerLoopState) {
    case ((counter, result), sublist) =>
      val innerLoopState = counter -> Vector.empty[(String, Int)]
      val (newCounter, subResult) = sublist.foldLeft(innerLoopState) {
        case ((counter, subResult), element) =>
          (counter + 1, subResult :+ (element, counter))
      }

      (newCounter, result :+ subResult.toList)
  }

  finalResult.toList
}

// scala> addIndeces(xs)
// res0: List[List[(String, Int)]] = List(List((a,0), (b,1)), List((c,2)), List((d,3), (e,4), (f,5)))

      

I have used Vector

for intermediate results to get a more efficient functional operation append

. With List

I would have to add and then cancel intermediate results.

+2


source


Plain non-tail recursive ...

 def zipFrom[A](start:Int)(l:List[A]):(List[(A,Int)],Int) = {
  val end = start + l.length
  val ys = l zip (start to end)
  ys -> end
 }

 def zp[A](xs:List[List[A]],acc:Int):List[List[(A,Int)]] = xs match {
  case Nil    => Nil
  case h :: t =>
   val (l,e) = zipFrom(acc)(h)
   l :: zp(t,e)
  }

      

+1


source


var index = 0
val lim = li.map {
  case l @ List(_*) =>
    val s = index
    index += l.length
    l.zip(s until index)
}

      

It works quickly and easily

0


source


by @Archetypal Paul using map instead

val ys = Iterator.from(0)
val zs = xs.map { _.map ((_,ys.next)) }

      

using zip and iterator and map

val ys = xs.flatten.zipWithIndex.iterator
val zs = xs.map { _.map ( x=> ys.next) }

      

0


source







All Articles