Join two lists with unequal length in Scala

Question

I have 2 lists:

val list_1 = List((1, 11), (2, 12), (3, 13), (4, 14))
val list_2 = List((1, 111), (2, 122), (3, 133), (4, 144), (1, 123), (2, 234))

I want to replace key in the second list as value of first list, resulting in a new list that looks like:

List ((11, 111), (12, 122), (13, 133), (14, 144), (11, 123), (12, 234))

This is my attempt:

object UniqueTest {
  def main(args: Array[String]){
     val l_1 = List((1, 11), (2, 12), (3, 13), (4, 14))
     val l_2 = List((1, 111), (2,122), (3, 133), (4, 144), (1, 123), (2, 234))
     val l_3 = l_2.map(x => (f(x._1, l_1), x._2))
     print(l_3)

  }
  def f(i: Int, list: List[(Int, Int)]): Int = {
    for(pair <- list){
      if(i == pair._1){
        return pair._2
      }
    }
    return 0
  }
}

This results in:

((11, 111), (12, 122), (13, 133), (14, 144), (11, 123), (12, 234))

Is the program above a good way to do this? Are there built-in functions in Scala to handle this need, or another way to do this manipulation?

Answer 1

The only real over-complication you make is this line:

val l_3 = l_2.map(x => (f(x._1, l_1), x._2))

Your f function uses an imperative style to loop over a list to find a key. Any time you find yourself doing this, it's a good indication what you want is a map. By doing the for loop each time you're exploding the computational complexity: a map will allow you to fetch the corresponding value for a given key in O(1). With a map you first convert your list, which is a key-value pair, to a datastructure explicit about supporting the key-value pair relationship.

Thus, the first thing you should do is build your map. Scala provides a really easy way to do this with toMap:

val map_1 = list_1.toMap

Then it is just a matter of 'mapping':

val result = list_2.map { case (key, value) => map_1.getOrElse(key, 0), value) }

This takes each case in your list_2, matches the first value (key) to a key in your map_1, retrieves that value (or the default 0) and puts as the first value in a key-value tuple.

Answer 2

You can do:

val map = l_1.toMap         // transform l_1 to a Map[Int, Int]
// for each (a, b) in l_2, retrieve the new value v of a and return (v, b)
val res = l_2.map { case (a, b) => (map.getOrElse(a, 0), b) }