CODEWITHSUNDEEP
scala
Sahand
Sahand

Reputation: 8360

Scala implicit ordering error when not specifying type parameters

  def merge(bigrams1: Map[String, mutable.SortedMap[String, Int]],
                    bigrams2: Map[String, mutable.SortedMap[String, Int]]): Map[String, mutable.SortedMap[String, Int]] = {
    bigrams2 ++ bigrams1
      .map(entry1 => entry1._1 -> (entry1._2 ++ bigrams2.getOrElse(entry1._1, mutable.SortedMap())
        .map(entry2 => entry2._1 -> (entry2._2 + entry1._2.getOrElse(entry2._1, 0)))))
  }

At compile time, I get these errors:

Error:(64, 114) diverging implicit expansion for type scala.math.Ordering[T1]
starting with method Tuple9 in object Ordering
    bigrams2 ++ bigrams1.map(entry1 => entry1._1 -> (entry1._2 ++ bigrams2.getOrElse(entry1._1, mutable.SortedMap()).map(entry2 => entry2._1 -> (entry2._2 + entry1._2.getOrElse(entry2._1, 0)))))
Error:(64, 114) not enough arguments for method apply: (implicit ord: scala.math.Ordering[A])scala.collection.mutable.SortedMap[A,B] in class SortedMapFactory.
Unspecified value parameter ord.
    bigrams2 ++ bigrams1.map(entry1 => entry1._1 -> (entry1._2 ++ bigrams2.getOrElse(entry1._1, mutable.SortedMap()).map(entry2 => entry2._1 -> (entry2._2 + entry1._2.getOrElse(entry2._1, 0)))))

Specifying the types of the sorted map solves the problem:

  def merge(bigrams1: Map[String, mutable.SortedMap[String, Int]],
                    bigrams2: Map[String, mutable.SortedMap[String, Int]]): Map[String, mutable.SortedMap[String, Int]] = {
    bigrams2 ++ bigrams1
      .map(entry1 => entry1._1 -> (entry1._2 ++ bigrams2.getOrElse(entry1._1, mutable.SortedMap[String, Int]())
        .map(entry2 => entry2._1 -> (entry2._2 + entry1._2.getOrElse(entry2._1, 0)))))
  }

Why do these type parameters need to be specified? Why can they not be inferred without problems with the implicit ordering?

Full code:

import java.io.File

import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.Source
import scala.util.matching.Regex

case class Bigrams(bigrams: Map[String, mutable.SortedMap[String, Int]]) {

  def mergeIn(bigramsIn: Map[String, mutable.SortedMap[String, Int]]): Bigrams = {
    Bigrams(Bigrams.merge(bigrams, bigramsIn))
  }

  def extractStatistics(path: String): Bigrams = {
    val entry: File = new File(path)
    if (entry.exists && entry.isDirectory) {
      val bigramsFromDir: Map[String, mutable.SortedMap[String, Int]] = entry
        .listFiles
        .filter(file => file.isFile && file.getName.endsWith(".sgm"))
        .map(Bigrams.getBigramsFrom)
        .foldLeft(Map[String, mutable.SortedMap[String, Int]]())(Bigrams.merge)
      val bigramsFromSubDirs: Bigrams = entry
        .listFiles
        .filter(entry => entry.isDirectory)
        .map(entry => extractStatistics(entry.getAbsolutePath))
        .foldLeft(Bigrams())(Bigrams.merge)
      bigramsFromSubDirs.mergeIn(bigramsFromDir)
    } else if (entry.exists && entry.isFile) {
      Bigrams(Bigrams.getBigramsFrom(entry))
    } else
    throw new RuntimeException("Incorrect path")
  }

  def getFreqs(word: String): Option[mutable.SortedMap[String, Int]] = {
    bigrams.get(word)
  }
}

object Bigrams {

  def fromPath(path: String): Bigrams = {
    new Bigrams(Map[String, mutable.SortedMap[String, Int]]()).extractStatistics(path)
  }

  def apply(): Bigrams = {
    new Bigrams(Map())
  }

  val BODY: Regex = "(?s).*<BODY>(.*)</BODY>(?s).*".r

  // Return a list with the markup for each article
  @tailrec
  def readArticles(remainingLines: List[String], acc: List[String]): List[String] = {
    if (remainingLines.size == 1) acc
    else {
      val nextLine = remainingLines.head
      if (nextLine.startsWith("<REUTERS ")) readArticles(remainingLines.tail, nextLine +: acc)
      else readArticles(remainingLines.tail, (acc.head + "\n" + nextLine) +: acc.tail)
    }
  }

  def merge(bigrams1: Map[String, mutable.SortedMap[String, Int]],
                    bigrams2: Map[String, mutable.SortedMap[String, Int]]): Map[String, mutable.SortedMap[String, Int]] = {
    bigrams2 ++ bigrams1
      .map(entry1 => entry1._1 -> (entry1._2 ++ bigrams2.getOrElse(entry1._1, mutable.SortedMap[String, Int]())
        .map(entry2 => entry2._1 -> (entry2._2 + entry1._2.getOrElse(entry2._1, 0)))))
  }

  def merge(bigrams1: Bigrams, bigrams2: Bigrams): Bigrams = {
    new Bigrams(merge(bigrams1.bigrams, bigrams2.bigrams))
  }

  def getBigramsFrom(path: File): Map[String, mutable.SortedMap[String, Int]] = {
    val file = Source.fromFile(path)
    val fileLines: List[String] = file.getLines().toList
    val articles: List[String] = Bigrams.readArticles(fileLines.tail, List())
    val bodies: List[String] = articles.map(extractBody).filter(body => !body.isEmpty)
    val sentenceTokens: List[List[String]] = bodies.flatMap(getSentenceTokens)
    sentenceTokens.foldLeft(Map[String, mutable.SortedMap[String, Int]]())((acc, tokens) => addBigramsFrom(tokens, acc))
  }

  def getBigrams(tokens: List[String]): List[(String, String)] = {
    tokens.indices.
      map(i => {
        if (i < tokens.size - 1) (tokens(i), tokens(i + 1))
        else null
      })
      .filter(_ != null).toList
  }

  // Return the body of the markup of one article
  def extractBody(article: String): String = {
    try {
      val body: String = article match {
        case Bigrams.BODY(bodyGroup) => bodyGroup
      }
      body
    }
    catch {
      case _: MatchError => ""
    }
  }

  def getSentenceTokens(text: String): List[List[String]] = {
    val separatedBySpace: List[String] = text
      .replace('\n', ' ')
      .replaceAll(" +", " ") // regex
      .split(" ")
      .map(token => if (token.endsWith(",")) token.init.toString else token)
      .toList

    val splitAt: List[Int] = separatedBySpace.indices
      .filter(i => i > 0 && separatedBySpace(i - 1).endsWith(".") || i == 0)
      .toList

    groupBySentenceTokens(separatedBySpace, splitAt, List()).map(sentenceTokens => sentenceTokens.init :+ sentenceTokens.last.substring(0, sentenceTokens.last.length - 1))
  }

  @tailrec
  def groupBySentenceTokens(tokens: List[String], splitAt: List[Int], sentences: List[List[String]]): List[List[String]] = {
    if (splitAt.size <= 1) {
      if (splitAt.size == 1) {
        sentences :+ tokens.slice(splitAt.head, tokens.size)
      } else {
        sentences
      }
    }
    else groupBySentenceTokens(tokens, splitAt.tail, sentences :+ tokens.slice(splitAt.head, splitAt.tail.head))
  }

  def addBigramsFrom(tokens: List[String], bigrams: Map[String, mutable.SortedMap[String, Int]]): Map[String, mutable.SortedMap[String, Int]] = {
    var newBigrams = bigrams
    val bigramsFromTokens: List[(String, String)] = Bigrams.getBigrams(tokens)

    bigramsFromTokens.foreach(bigram => { // TODO: This code uses side effects to get the job done. Try to remove them.
      val currentFreqs: mutable.SortedMap[String, Int] = newBigrams.get(bigram._1)
        .map((map: mutable.SortedMap[String, Int]) => map)
        .getOrElse(mutable.SortedMap())
      val incrementedWordFreq = currentFreqs.get(bigram._2)
        .map(freq => freq + 1)
        .getOrElse(1)

      val newFreqs = currentFreqs + (bigram._2 -> incrementedWordFreq)
      newBigrams = newBigrams - bigram._1 + (bigram._1 -> newFreqs)
    })
    newBigrams
  }
}

Upvotes: 2

Views: 228

Answers (1)

Dmytro Mitin
Dmytro Mitin

Reputation: 51658

The thing is that method Map#getOrElse in 2.13 (or MapLike#getOrElse in 2.12) has signature

def getOrElse[V1 >: V](key: K, default: => V1): V1

https://github.com/scala/scala/blob/2.13.x/src/library/scala/collection/Map.scala#L132-L135

https://github.com/scala/scala/blob/2.12.x/src/library/scala/collection/MapLike.scala#L129-L132

i.e. it expects not necessarily default of the same type as V in Map[K, +V] (or MapLike[K, +V, +This <: MapLike[K, V, This] with Map[K, V]]) but possibly of a supertype of V. In your case V is mutable.SortedMap[String, Int] and there are so many its supertypes (you can look at inheritance hierarchy yourself). mutable.SortedMap() can be of any type mutable.SortedMap[A, B] or their super types.

If you replace method getOrElse with having fixed V

implicit class MapOps[K, V](m: Map[K, V]) {
  def getOrElse1(key: K, default: => V): V = m.get(key) match {
    case Some(v) => v
    case None => default
  }
}

or in 2.12

implicit class MapOps[K, V, +This <: MapLike[K, V, This] with Map[K, V]](m: MapLike[K, V, This]) {
  def getOrElse1(key: K, default: => V): V = m.get(key) match {
    case Some(v) => v
    case None => default
  }
}

then in your code 

... bigrams2.getOrElse1(entry1._1, mutable.SortedMap())

all types will be inferred and it will compile.

So sometimes types should be just specified explicitly when compiler asks.

Upvotes: 1

Related Questions