CODEWITHSUNDEEP
scalafunctional-programmingscala-collections
foxtrotuniform6969
foxtrotuniform6969

Reputation: 4125

Scala: Compare elements at same position in two arrays

I'm in the process of learning Scala and am trying to write some sort of function that will compare one element in an list against an element in another list at the same index. I know that there has to be a more Scalatic way to do this than two write two for loops and keep track of the current index of each manually.

Let's say that we're comparing URLs, for example. Say that we have the following two Lists that are URLs split by the / character:

val incomingUrl = List("users", "profile", "12345")

and

val urlToCompare = List("users", "profile", ":id")

Say that I want to treat any element that begins with the : character as a match, but any element that does not begin with a : will not be a match.

What is the best and most Scalatic way to go about doing this comparison?

Coming from a OOP background, I would immediately jump to a for loop, but I know that there has to be a good FP way to go about it that will teach me a thing or two about Scala.

EDIT

For completion, I found this outdated question shortly after posting mine that relates to the problem.

EDIT 2

The implementation that I chose for this specific use case:

def doRoutesMatch(incomingURL: List[String], urlToCompare: List[String]): Boolean = {
    // if the lengths don't match, return immediately
    if (incomingURL.length != urlToCompare.length) return false

    // merge the lists into a tuple
    urlToCompare.zip(incomingURL)
      // iterate over it
      .foreach {
        // get each path
        case (existingPath, pathToCompare) =>
          if (
             // check if this is some value supplied to the url, such as `:id`
             existingPath(0) != ':' && 
             // if this isn't a placeholder for a value that the route needs, then check if the strings are equal
             p2 != p1
             ) 
             // if neither matches, it doesn't match the existing route
             return false
      }

   // return true if a `false` didn't get returned in the above foreach loop
   true
}

Upvotes: 1

Views: 1296

Answers (3)

Andronicus
Andronicus

Reputation: 26076

You can use zip, that invoked on Seq[A] with Seq[B] results in Seq[(A, B)]. In other words it creates a sequence with tuples with elements of both sequences:

incomingUrl.zip(urlToCompare).map { case(incoming, pattern) => f(incoming, pattern) }

Upvotes: 3

Allen Han
Allen Han

Reputation: 1163

Since the OP is curious to see how we would use lazy collections or a custom fold to do the same thing, I have included a separate answer with those implementations.

The first implementation uses lazy collections. Note that lazy collections have poor cache properties so that in practice, it often does does not make sense to use lazy collections as a micro-optimization. Although lazy collections will minimize the number of times you traverse the data, as has already been mentioned, the underlying data structure does not have good cache locality. To understand why lazy collections minimize the number of passes you make over the data, read chapter 5 of Functional Programming in Scala.

object LazyZipTest extends App{
  val incomingUrl = List("users", "profile", "12345", "extra").view

  val urlToCompare = List("users", "profile", ":id").view

  val list1 = incomingUrl.map(Some(_))
  val list2 = urlToCompare.map(Some(_))

  val zipped = list1.zipAll(list2, None, None)

  println(zipped)
}

The second implementation uses a custom fold to go over lists only one time. Since we are appending to the rear of our data structure, we want to use IndexedSeq, not List. You should rarely be using List anyway. Otherwise, if you are going to convert from List to IndexedSeq, you are actually making one additional pass over the data, in which case, you might as well not bother and just use the naive implementation I already wrote in the other answer.

Here is the custom fold.

object FoldTest extends App{

  val incomingUrl = List("users", "profile", "12345", "extra").toIndexedSeq

  val urlToCompare = List("users", "profile", ":id").toIndexedSeq

  def onePassZip[T, U](l1: IndexedSeq[T], l2: IndexedSeq[U]): IndexedSeq[(Option[T], Option[U])] = {
    val folded = l1.foldLeft((l2, IndexedSeq[(Option[T], Option[U])]())) { (acc, e) =>
      acc._1 match {
        case x +: xs => (xs, acc._2 :+ (Some(e), Some(x)))
        case IndexedSeq() => (IndexedSeq(), acc._2 :+ (Some(e), None))
      }
    }
    folded._2 ++ folded._1.map(x => (None, Some(x)))
  }

  println(onePassZip(incomingUrl, urlToCompare))
  println(onePassZip(urlToCompare, incomingUrl))
}

If you have any questions, I can answer them in the comments section.

Upvotes: 0

Allen Han
Allen Han

Reputation: 1163

There is already another answer to the question, but I am adding another one since there is one corner case to watch out for. If you don't know the lengths of the two Lists, you need zipAll. Since zipAll needs a default value to insert if no corresponding element exists in the List, I am first wrapping every element in a Some, and then performing the zipAll.

object ZipAllTest extends App {
  val incomingUrl = List("users", "profile", "12345", "extra")

  val urlToCompare = List("users", "profile", ":id")

  val list1 = incomingUrl.map(Some(_))
  val list2 = urlToCompare.map(Some(_))

  val zipped = list1.zipAll(list2, None, None)

  println(zipped)
}

One thing that might bother you is that we are making several passes through the data. If that's something you are worried about, you can use lazy collections or else write a custom fold that makes only one pass over the data. That is probably overkill though. If someone wants to, they can add those alternative implementations in another answer.

Upvotes: 1

Related Questions