CODEWITHSUNDEEP
scalacollections
West_JR
West_JR

Reputation: 434

scala collections : map a list and carry some state?

I seem to run into this problem all the time. I want to modify some of the elements in a list, but I need to keep some state as I do it, so map doesn't work.

Here is an example :

scala> val l1 = List("a","b","c","d","e","f","b","c","e","b","a")
l1: List[String] = List(a, b, c, d, e, f, b, c, e, b, a)

I want to change the name of any duplicates. so I want to end up with this:

List(a1, b1, c1, d, e1, f, b2, c2, e2, b3, a2)

Getting the dupes is easy :

scala> val d = l1.diff(l1.distinct).distinct
d: List[String] = List(b, c, e, a)

Now I'm stuck. I made it work by converting d to a HashMap w/ a count, and writing a function to iterate over l1 and update it & the hash before recursing. Which works fine, but looks kinda ugly to me.

But I've always thought there should be a way to do w/ the collection classes.

Here is the rest of my solution which I don't like :

  val m = d.map( _ -> 1).toMap

  def makeIt(ms: Map[String, Int], ol: Iterator[String], res: List[String]=List[String]()) :List[String] = {
    if( !ol.hasNext) return res
    val no = ol.next()
    val (p,nm) = ms.get(no) match {
      case Some(v) => (s"$no$v", ms.updated(no,v+1))
      case None => (no,ms)
    }

    makeIt(nm,ol,res :+ p)
  }

  makeIt(m,l1.iterator)

Which gives me what I want

res2: List[String] = List(a1, b1, c1, d, e1, f, b2, c2, e2, b3, a2)

I feel like I want "mapWithState" where I can just pass something along. Like Fold-ish. Maybe it exists and I just haven't found it yet?

Thanks

-------UPDATE---------

@Aluan Haddad's comment pointed me in this direction. Which destroys order, which is fine for my case. But the "state" is carried by zipWithIndex. I'm looking for a more general case where the state would require some computation at each element. But for this simple case I like it :

l1.groupBy(x=>x).values.flatMap( v =>{
    if( v.length <= 1 ) v else {
      v.zipWithIndex.map{ case (s,i) => s"$s${i+1}"}
    }
  })
res7: Iterable[String] = List(e1, e2, f, a1, a2, b1, b2, b3, c1, c2, d)

Upvotes: 3

Views: 1078

Answers (2)

Tim
Tim

Reputation: 27356

A simple but slow version

l1.zipWithIndex.map{ case (elem, i) =>
  if (l1.count(_ == elem) == 1) {
    elem
  } else {
    val n = {l1.take(i+1).count(_ == elem)}
    s"$elem$n"
  }
}

The next version is longer, less pretty, and not functional, but should be faster in the unlikely case that you are processing a very long list.

def makeUniq(in: Seq[String]): Seq[String] = {
  // Count occurrence of each element
  val m = mutable.Map.empty[String, Int]

  for (elem <- in) {
    m.update(elem, m.getOrElseUpdate(elem, 0) + 1)
  }

  // Remove elements with a single occurrence
  val dupes = m.filter(_._2 > 1)

  // Apply numbering to duplicate elements
  in.reverse.map(e => {
    val idx = dupes.get(e) match {
      case Some(i) =>
        dupes.update(e, i - 1)
        i.toString
      case _ =>
        ""
    }

    s"$e$idx"
    }).reverse
  }

The code is easier if you wanted to apply a count to every element rather than just the non-unique ones.

def makeUniq(in: Seq[String]): Seq[String] = {
  val m = mutable.Map.empty[String, Int]

  in.map{ e =>
    val i = m.getOrElseUpdate(e, 0) + 1
    m.update(e, i)

    s"$e$i"
  }
}

Upvotes: 1

jwvh
jwvh

Reputation: 51271

The tricky part is that the "d" and "f" elements get no modification.

This is what I came up with. It's a bit more concise, code wise, but does involve multiple traversals.

val l1: List[String] = List("a","b","c","d","e","f","b","c","e","b","a")

l1.reverse.tails.foldLeft(List[String]()){
  case (res, Nil) => res
  case (res, hd::tl) =>
    val count = tl.count(_ == hd)
    if (count > 0) s"$hd${count+1}" +: res
    else if (res.contains(hd+2)) (hd+1) +: res
    else hd +: res
}
//res0: List[String] = List(a1, b1, c1, d, e1, f, b2, c2, e2, b3, a2)

By using tails, each element, hd, is able to see the future, tl, and the past, res.

Upvotes: 2

Related Questions