soote soote - 3 months ago 8
Scala Question

Combine 2 vectors of a custom type to return 1 vector

I have a class:

case class Custom(label: String, num: Long)


Given these two lists:

val l1 = Vector(Custom("a", 1), Custom("aa", 1))
val l2 = Vector(Custom("a", 1))


I wish to obtain the resulting list:

val l3 = Vector(Custom("a", 2), Custom("aa", 1))


I've attempted using fold like so:

l1.foldLeft(l2)((acc: List[Custom], el: Custom) => {
val itemWithIndex: Option[(Custom, Int)] = acc.zipWithIndex.find(_._1.label == el.label)
itemWithIndex match {
case Some(x) => acc.updated(x._2, Custom(el.label, acc(x._2).num + el.num))
case None => el :: acc
}
})


This implementation iterates the accumulator(
l2
) 3 times, and the
l1
once. I'm looking for a more efficient solution.




After some simple benchmarking (I ran both functions
10000000
times with the same input), the fold solution appears to be slightly faster then the concat + groupBy solution I've answered with. I plan to make a better benchmark with randomized inputs in the near future.

I'll keep this question open for a while in case anyone wishes to find a more efficient solution.

Answer
 import scalaz.syntax.monoid._
  case class Custom(label: String, num: Long)
  val l1 = Vector(Custom("a", 1), Custom("aa", 1))
  val l2 = Vector(Custom("a", 1))

  def toM(v: Vector[Custom]): Map[String, Long] = {
    (v map (cus ⇒ cus.label → cus.num)).toMap
  }

  def fromM(m: Map[String, Long]): Vector[Custom] = {
    m.map{case (l , num) ⇒ Custom(l, num)}.toVector
  }

  implicit val myMonoid = new Monoid[Vector[Custom]] {
    import scalaz.std.anyVal.longInstance
    val mm = scalaz.std.map.mapMonoid[String, Long]

    override def zero: Vector[Custom] = fromM(mm.zero)

    override def append(f1: Vector[Custom], f2: ⇒ Vector[Custom]): Vector[Custom] = fromM(mm.append(toM(f1), toM(f2)))
  }



  println(l1 |+| l2) \\Vector(Custom(a,2), Custom(aa,1))

If you want to be more clear, you can extract toM and fromM to Isomorphism instance.