Scala library for typical algorithms

Libraries
1

Is there a scala library for common algorithms?

such as “finding the common prefix” of a list of strings (or any other type)?

I am aware it’s simple to implement a function for “finding the common prefix”, and here there are a few implementations. However, I am asking for a library with common algorithms to avoid reinventing the wheel.

2

Scala uses Java’s strings so if you’re very keen on finding a library you can also look for Java library. There are just a few extra steps to use Java library:

  1. import scala.collection.JavaConverters._
  2. Use .asScala and .asJava to convert between collection types, i.e.
    val result = SomeJavaUtil.findCommonPrefix(Seq("hey", "ho").asJava)

I don’t think such pretty niche function could have a well supported specialized library, but you can look for it. Anyway, I’m posting here my imperative and somewhat optimized version of max LCP finder:

object LCP {
  def longestCommonPrefix(strings: String*): String = {
    if (strings.isEmpty) {
      ""
    } else {
      var maxLcpSize = strings.view.map(_.length).min
      val firstString = strings.head
      for (currentString <- strings.view(1, strings.length)) {
        var currentLcpSize = 0
        while (currentLcpSize < maxLcpSize &&
               firstString(currentLcpSize) == currentString(currentLcpSize)) {
          currentLcpSize += 1
        }
        maxLcpSize = currentLcpSize
      }
      firstString.substring(0, maxLcpSize)
    }
  }

  def main(args: Array[String]): Unit = {
    println(longestCommonPrefix("hey", "ho", "hay", "hh"))
    println(longestCommonPrefix("seq 1", "seq 2", "se 3"))
    println(longestCommonPrefix("seq1.", "seq2.", "seq3."))
  }
}

That is pretty much asymptotically optimal (I think) if the strings are unrelated. If, however, those strings are e.g. rotations of a single input string (as in case of Burrows Wheeler Transform) then there exist algorithms that can exploit that fact for improved performance.