Gerome Pistre Gerome Pistre - 3 months ago 5
Scala Question

Scala return value different than expected

I'm learning Scala and writing a function (recursive) to count the number of parentheses: +1 for opening, -1 for closing, in order to match and balance all the parentheses in a list of chars. It should return 0 is the parentheses are balanced.

I came up with that (with numerous print statements to understand what's going on):

def countPar(charList: List[Char], count: Int): Int = {

if (count < 0) {
println("negative count, returning", count)
count
}
else if (charList.isEmpty) {
println("empty list, returning", count)
count
}
else if (charList.head.equals('(')) {
println("head is ", charList.head, " count + 1:", count + 1)
count + countPar(charList.tail, count + 1)
}
else if (charList.head.equals(')')) {
println("head is ", charList.head, " count - 1:", count - 1)
count + countPar(charList.tail, count - 1)
}
else {
println("head is ", charList.head, " count:", count)
countPar(charList.tail, count)
}
}

val parCount = countPar("(a(b)c)".toList, 0)

println(parCount)


And the print statements do seem to confirm that the logic is working, yet the final return value is wrong...

(head is ,(, count + 1:,1)
(head is ,a, count:,1)
(head is ,(, count + 1:,2)
(head is ,b, count:,2)
(head is ,), count - 1:,1)
(head is ,c, count:,1)
(head is ,), count - 1:,0)
(empty list, returning,0)
parCount: Int = 4


What am I missing?

Answer

The issue is simply returning count + countPar(charList.tail, count + 1) instead of countPar(charList.tail, count + 1) (and similarly for closing parenthesis).

The point of your recursive function is that you update the count according to the head value, and pass it to the recursive call which will update it based on the tail value (and the recursive call will do the same thing, until the tail is empty). That means that the recursive call will return the correct result: no need to add anything to it.

edit: I think it also becomes clearer once refactored like so (the important part is the one with the comment, I tried not to change your approach otherwise):

def countPar(charList: List[Char], count: Int): Int = {
  if (count < 0) {
    println("negative count, returning", count)
    count
  } else if (charList.isEmpty) {
    println("empty list, returning", count)
    count
  } else {
    val updatedCount =
      if (charList.head.equals('('))
        count + 1
      else if (charList.head.equals(')'))
        count - 1
      else
        count
    println(s"head is ${charList.head}, count: ${updatedCount}")
    // We see here that the reursive call is the same in the 3 cases: the
    // only difference is how we update the count
    countPar(charList.tail, updatedCount)
  }
}
Comments