Kauber Kauber - 1 month ago 9
Scala Question

trying to understand parenthesis balancing recursion in scala

New to scala and functional programming.
Disclaimer: yes, I am taking the scala course on coursera, and yes, this is part of the assignment. My only goal here is to get some help to understand how this solution works in order to develop my own solution and familiarize with functional programming.

I am stuck since 2 days on this implementation of the recursive algorithm to check for parenthesis balancing. I simply don't get:
1. how the functions are structured
2. how the evaluation of the boolean expression occurs

def balance(chars: List[Char]): Boolean = {
def balanced(chars: List[Char], open: Int): Boolean = {
if (chars.isEmpty) open == 0
else
if (chars.head == '(') balanced(chars.tail,open+1)
else
if (chars.head == ')') open>0 && balanced(chars.tail,open-1)
else balanced(chars.tail,open)
}
balanced(chars,0)
}


My first doubt is the following. The inner function immediately starts by evaluating the boolean expression

if (chars.isEmpty) open == 0


My understanding (maybe wrong) is that here both expressions will be evaluated:
chars.isEmpty
and
open==0
.
However, the argument
open
doesn't seem to be yet defined anywhere. So why don't I get an error?
Second, I simply cannot get the line:

if (chars.head == '(') balanced(chars.tail,open+1)


Where will
balanced(chars.tail,open+1)
be evaluated and how?

Suppose I want to check whether
"("
has balanced parentheses.

if (chars.isEmpty) open == 0


Will return False, then

if (chars.head == '(') balanced(chars.tail,open+1)


The first expression will be TRUE, but the second one?
"(" doesn't have a tail, and again I don't see how
open+1
works, since the integer
open
has not been defined anywhere.
I am pretty confused, any clarification?

Answer Source

You are misunderstanding one of the fundamental things - function definitions. Let's skip initially unimportant part of a program:

def balance(chars: List[Char]): Boolean = {
  def balanced(chars: List[Char], open: Int): Boolean = { /* ... */ }
  balanced(chars,0)
}

Notice that the first line of balance function is just a function definition - its a local function. Once control flow hits the balanced(chars, 0) line it'll invoke this function - thus open variable would get initialized to 0.

Hopefully that solves your "uninitialized variable" concerns. If you have any more questions just comment and I'll try to help you further.