Friday, May 30, 2014

Case study in Scala: Avoiding imperative programming (does it pay off?) -> Part 1, The Ugly

Just for fun, let's consider the imperative example of counting words in a string, as presented in the Chapter 17 of Programming in Scala book by Odersky et al. In it, we have:

scala> def countWords(text: String) = {
  val counts = mutable.Map.empty[String, Int]
  for (rawWord <- text.split("[ !.,]+")) {
    val word = rawWord.toLowerCase
    val oldCount =
      if (counts.contains(word)counts(word)
      else 0
    counts += (word -> (oldCount + 1))
  }
  counts
}
countWords: (String)scala.collection.mutable.Map[String,Int]
 

scala> countWords("See Spot run! Run, Spot. Run!")
res30: scala.collection.mutable.Map[String,Int] =
Map(see -> 1, run -> 3, spot -> 2)
 

Let's try and do it in a recursive/functional way, without mutable Maps:

scala> def countWords(s:String):Map[String,Int] = {
   def countW(str:List[String], 

              acc:Map[String,Int]):Map[String,Int] = {
     if (str.isEmpty)
       acc
     else {
       val k = str.head
       if (acc.contains(k)) {
         val wCtr = acc(k)+1
         countW(str.tail,acc-k+(k->wCtr))
       } else
        countW(str.tail,acc+(k->1))
     }
   }
  countW(s.split("[ !,.]+").toList,Map[String,Int]())
}
 

scala> countWords("See Spot run! Run, Spot. Run!")
res21: Map[String,Int] = Map(see -> 1, spot -> 2, run -> 3)

Neither of these implementations are pretty. The recursive one essentially does the same thing as the iterative one but it does it in a "clunkier" way - we actually have to throw out the (String,count) pair and re-add it every time the same word is encountered. However, it does the job,

Let's see if we can improve on this in the next installment.

No comments: