How to write nested loops in idiomatic Scala?

Question

This is my pseudo code, obviously this is not idiomatic scala as I use a lot of mutable variables and loops.

My goal is to transform this into idiomatic scala in a functional way.

The objective of the algorithm is that given a list of strings, do a N^2 comparison on itself to find matches using edit distance. Because edit distance checks are example, I want to avoid doing edit distance checks on string pairs that have been checked.

def pairwisecomp(block: Iterable[String]): List[(String, String)] = {
    var matches = new ListBuffer[(String, String)]

    // pseudo code; not intended to be valid scala
    for (var i = 0; i < block.size; i++) {
       val str1 = block[i]
       // iterate from i because no need to go backwards to compare
       for (var j = i+1; j < block.size; j++) {
           val str2 = block[j]
           // check edit distance
           // if less than 2, append into the matches
           if (editDistance(str1, str2) < 2) {
              matches.append((str1, str2))
           }
       }
    }


    return matches.toList
  }

suish · Accepted Answer · 2016-10-24 01:31:52Z

3

I assume it can be shortened though, I think the code blow is doing exactly the same as you wrote.

block.flatMap{ str1 =>
  block.zipWithIndex.filter{ case (elem,index) => index > i}.map{ case (str2,index) =>
    ((str1,str2),editDistance(str1,str2) < 2)
  }.filter{_.2}.map{_1}
}.toList

EDIT: It maybe simpler in for-comprehensions.

val b = block.zipWithIndex
(for {
  (str1,outerIndex) <- b
  (str2,innerIndex) <- b if innerIndex > outerIndex && editDistance(str1,str2) < 2
} yield (str1,str2)).toList

edited Oct 24, 2016 at 1:31

answered Oct 24, 2016 at 0:49

suish

3,3631 gold badge19 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

samol Over a year ago

block.zipWithIndex.filter{ case (elem,index) => index > i} so for nested loops this is the right away to start iterating at a certain index?

samol Over a year ago

Don't you need to do block.view.zipWithIndex instead?

suish Over a year ago

actually, scala for is just an syntax sugar of foreach,flatMap,map and filter method. in another way to say, the code can be written as for-comprehensions.and I guess block.view.zipWithIndex is slower because the loop looks all the values in it.

jwvh · Accepted Answer · 2016-10-24 01:23:59Z

1

Without a working editDistance() to test with it's hard to know, but I think this is close to what you're after.

def pairwisecomp(block: Seq[String]): List[List[String]] = {
  block.combinations(2).filter(editDistance(str1, str2) < 2).toList
}

Note that I changed the block collection type so that I can use the combinations() method. There are other ways to achieve this.

answered Oct 24, 2016 at 1:23

jwvh

51.3k7 gold badges42 silver badges70 bronze badges

Comments

Iadams · Accepted Answer · 2016-10-24 08:12:56Z

1

'tails' is your friend:

   def tryIt(): Unit = {
    def editDistance(v1: (String, Int), v2: (String, Int)): Int = {
      val (_, d1) = v1
      val (_, d2) = v2
      Math.abs(d1-d2)
    }
    val src = Seq (("C", 3), ("D", 4), ("A", 1), ("B", 2), ("E", 5), ("F", 6))
    val res = for {
      (h::tl) <- src.tails
      t <- tl if editDistance(h ,t) < 2
    } yield (h,t)
    res.foreach {case (r1, r2) => println(s"$r1, $r2")}
  }

(h::tl) is a series of each element (h) in the input plus everything following it (tl). From that you compare each element 't' in the tail sequence tl. If 'h' and 't' are close enough, yield that pair.

answered Oct 24, 2016 at 8:12

Iadams

5463 silver badges7 bronze badges

Comments

shingekinolinus · Accepted Answer · 2016-10-24 10:09:16Z

1

I think you can use a for-comprehension for this:

def pairwisecompII(block: Vector[String]): Seq[(String, String)] = {
  for {
    i ← block.indices
    str1 = block(i)
    j ← i + 1 until block.size
    str2 = block(j)
    if editDistance(str1, str2) < 2
  } yield (str1, str2)
}

answered Oct 24, 2016 at 10:09

shingekinolinus

1291 silver badge8 bronze badges

Collectives™ on Stack Overflow

How to write nested loops in idiomatic Scala?

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related