Compressing string in Scala, how to do this immutably?

Question

I have a string "abbbbccdddd" and the function should return "a1b4c2d4".

This is what I have written in Scala.

Iterative-version

def compress(str: String) = {
  val chars = List(str).flatten.map(_.toString) ++ List(null)
  var result: String = ""

  var lookBack: String = chars.head
  var occurance: Int = 0

  chars.foreach { c =>
    if (c != lookBack) {
      result = result + lookBack.toString + occurance
      occurance = 0
    }

    occurance = occurance + 1
    lookBack = c
  }

  result
}

Recursive-version

def compress(str: String): String = {
  def compressHandler(str: String, lookBack: String, occurance: Int, result: String): String = {
    if(str.isEmpty) {
      result
    } else if(str.head.toString == lookBack) {
      compressHandler(str.drop(1), str.head.toString, occurance + 1, result)
    } else {
      compressHandler(str, str.head.toString, 0, result + lookBack + occurance)
    }
  }

  compressHandler(str + "0", str.head.toString, 0, "")
}

Scala — being a functional language should have much better solutions!

How to improve second (by somehow using map/reduce/fold) and how to do the first following concept of immutability (purely functional)?

Answer 1

Here's my take using foldLeft:

def compress(s: String) = {
    val a : List[(Char,Int)] = List()
    s.toCharArray.foldLeft(a)((acc, elem) => acc match {
        case Nil => (elem, 1) :: Nil
        case (a, b) :: tail =>
            if (a == elem) (elem, b + 1) :: tail else (elem, 1) :: acc
    }).reverse
    .map{ case (a, b) => a.toString + b }
    .mkString("")
}

Note: I have assumed that order matters. That is, aabbbaa will reduce to a2b3a2

Answer 2

I would suggest omitting the allocation of extra space. Try to start with:

object Solution:
  def compress(str: String): String =
    val (sb, _) = 
      Vector.range(0, str.size + 1).foldLeft(StringBuilder(), 0) { 
        case ((sb, occurance), i) =>
          if i == 0
            ???
          else if i == str.size
            ???
          else if str(i) == str(i - 1)
            ???
          else
            ???
      }
    sb.toString