3

I am 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 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.

Improve this question
3
  • What do you mean when you say that open is not defined? It's one of the function's parameters. Commented Jul 2, 2017 at 16:32
  • Yes but no value has been assigned to it. How can I know if open == 0 if open didn't take on any value so far? Commented Jul 2, 2017 at 16:33
  • By the same logic you could argue that you don't know what the value of chars is. A function's body is not evaluated until the function is called. And once that happens, you do know what the arguments are. Commented Jul 2, 2017 at 16:35

1 Answer 1

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you, that was helpful to solve the first important doubt I had. I still don't get how if (chars.head == '(') balanced(chars.tail,open+1) is evaluated. How can balanced(chars.tail,open+1) can be evaluated as a boolean? If I have, as mentioned, "(", the first expression will give True, but I don't see how to reduce the second. Thanks a lot for your help
@Kauber Hm, not sure what you are missing there - balanced(chars.tail, open + 1) is just a function call - to a function that returns a boolean. It just works exactly the same as in any other programming language.
I think I got it know, I see what a function call is, but as said in the original post, I was really confused about the structure of the function. Thank you again
@Kauber Also note that if (chars.head == '(') balanced(chars.tail,open+1) is not evaluated by itself without the else part; this is like asking how is 2 + evaluated.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.