Style
Type inference
Scala supports type inference. Explicitly annotating the type of something whose type is obvious does not improve readability. You should annotate the types of your public APIs, but other than that, you should use type inference as far as possible, as long as it doesn't impact readability.
For example, this:
val OPEN_PARENTHESIS: Char = '('
val CLOSED_PARENTHESIS: Char = ')'
should just be
val OPEN_PARENTHESIS = '('
val CLOSED_PARENTHESIS = ')'
Constant value definitions
If you intend for these to be constant value definitions, then they need to be explicitly marked as final, and they must not have a type annotation:
final val OPEN_PARENTHESIS = '('
final val CLOSED_PARENTHESIS = ')'
(Assuming this is code nested within some sort of main object, for example.)
Local functions
The most widely-used style for helper functions of recursive methods is to nest those helpers as local functions into the recursive method like this:
def someComputation(externallyVisibleParameter: SomeType) =
def someComputationRec(internalParameter: SomeOtherType): ReturnType =
// do your recursive thing
someComputationRec(foo)
You could do that with isBalanced (which is only used within balance) and processChar (which is only used within isBalanced).
This keeps your external API clean of any helpers that nobody else needs to know about.
Naming
I find balance to be a strange name for a method that tells you whether something is balanced. It sounds more like an action than a predicate, i.e. like a function which balances something instead of telling you whether it is balanced.
A more idiomatic name for such a predicate function would be isBalanced.
Lightweight control syntax
You use the new-style Scala 3 lightweight control syntax for your pattern matching and you use the indentation-based syntax for your methods. However, for some reason, you do not use it for the exception handling.
This:
case x :: xs =>
try {
val nextStack = processChar(x, stack)
isBalanced(xs, nextStack)
} catch {
case e: Exception => false
}
could be written like this:
case x :: xs =>
try
val nextStack = processChar(x, stack)
isBalanced(xs, nextStack)
catch
case e: Exception => false
or
case x :: xs =>
try
val nextStack = processChar(x, stack)
isBalanced(xs, nextStack)
catch case e: Exception => false
Readability
Do you really think that OPEN_PARENTHESIS is more readable than '('? How likely do you think it is that someone who reads your code knows what an open parenthesis is, but doesn't know that ( is an open parenthesis?
Pattern matching
There is a place where you use pattern matching in a weird manner:
char match
case char if char == '(' => stack.push(char)
case char if char == ')' => stack.tail
case _ => throw new IllegalArgumentException("The given char is not valid")
So, you are matching against the value of the variable char, you don't care what its value is, but you assign it to a new variable named char which shadows the outer variable named char and then you guard the pattern such that the pattern only matches if the value of this new variable named char is equal to an open parenthesis.
Soooooo … in other words, you are matching an open parenthesis? Then why not just say so:
char match
case '(' => stack.push(char)
case ')' => stack.tail
case _ => throw new IllegalArgumentException("The given char is not valid")
Pokémon Exceptions
This
case e: Exception => false
is called the Pokémon Exception Handling Anti-Pattern ("Gotta catch 'em all"), also known as Diaper Exception Handling ("Catches all the shit"). It is a serious anti-pattern, and should never be used.
What you are essentially saying is "Whatever is going wrong, I know 100% how to correctly handle it". But do you, really? Are you 100% sure that the correct result of a NullPointerException is that the string is unbalanced?
You should only ever catch exceptions that you
- Expect AND
- Know how to handle
If you don't know how to handle an exception, don't handle it. Let someone else deal with it. If you don't expect an exception, don't waste effort on handling it. It shouldn't be there in the first place, and if it is there, something has gone wrong that you don't understand, so how can you sensibly deal with it?
So, you should catch the exception as narrow as possible:
case _: IllegalArgumentException => false
In fact, with your Pokémon Exception Handling, you have covered up a bug: in processChar you take the tail of the stack without checking whether there is even something on the stack. This results in an UnsupportedOperationException which is swallowed by your Pokémon Handler.
It just happens to work because trying to pop an element off an empty stack means that you have more closing parenthesis than opening ones, which makes the string unbalanced, but that is a very roundabout reasoning that is not made clear anywhere in the code.
It deserves at least an explicit mention, and probably some comments as well:
case _: IllegalArgumentException | _: UnsupportedOperationException => false
Functional programming
Immutable data structures
The obvious red flag in your code when it comes to functional programming is the use of a mutable data structure, in particular, the mutable stack.
You already pass the stack as an argument everywhere, so it would be easy to replace it with an immutable stack (which is just a list) – you just need to also return the modified version everywhere:
def isBalanced(chars: List[Char]): Boolean =
def isBalancedRec(chars: List[Char], stack: List[Char]): Boolean =
def processChar(char: Char) = char match
case '(' => char :: stack
case ')' => stack.tail
case _ => throw new IllegalArgumentException("The given char is not valid")
chars match
case Nil => stack.isEmpty
case x :: xs =>
try
val nextStack = processChar(x)
isBalanced(xs, nextStack)
catch case _: IllegalArgumentException | _: UnsupportedOperationException => false
val parentheses = chars.filter(char => char == '(' || char == ')')
val emptyStack = List.empty[Char]
isBalancedRec(parentheses, emptyStack)
Exceptions
The slightly less obvious red flag is your use of exceptions. Functional programmers prefer to write functions that don't fail. Scala's standard library has multiple types that could help you here:
These types have the advantage over exceptions that they are composable, meaning you can build up more complex behaviors from simple ones. Option and Try are also monads and behave like collections, meaning you can use all the tools you already know from processing collections.
So, you could rewrite your code something like this:
def isBalanced(chars: List[Char]): Boolean =
def isBalancedRec(chars: List[Char], stack: List[Char]): Boolean =
def processChar(char: Char) = char match
case '(' => Some(char :: stack)
case ')' if stack.nonEmpty => Some(stack.tail)
case _ => None
chars match
case Nil => stack.isEmpty
case x :: xs =>
processChar(x) match
case Some(nextStack) => isBalancedRec(xs, nextStack)
case None => false
val parentheses = chars.filter(char => char == '(' || char == ')')
val emptyStack = List.empty[Char]
isBalancedRec(parentheses, emptyStack)
Better API
Requiring the user to pass what is basically a string as a List[Char] is weird. Why not allow them to pass it as a string?
You can still use your list-based representation internally by simply converting the string to a list at the beginning of the method. Alternatively, you can re-write the list pattern matching using string pattern matching.
Better internal API
As mentioned by Sara, the way processChar interacts with the rest is strange. With a name like processChar, I would expect it to, you know, process any character. But actually, it only processes parentheses and fails with an exception (in your original code) or a None (in mine) when it encounters anything else. Why not simply ignore anything that is not a parenthesis?
Also, as mentioned by Sara, at no point is it actually important what the stack contains. The only thing that is relevant is the height of the stack, which corresponds to the nesting depth of the parentheses.
An implementation that uses the nesting depth could look something like this:
def isBalanced(str: String) =
def isBalancedRec(s: String = str, depth: Int = 0): Boolean =
s match
case "" => depth == 0
case s"($rest" => isBalancedRec(rest, depth + 1)
case s")$rest" => depth > 0 && isBalancedRec(rest, depth - 1)
case _ => isBalancedRec(s.drop(1), depth)
isBalancedRec()
Recursion Patterns
In FP, there are a number of well-known recursion patterns. They are actually more than well-known and more than patterns, they have solid mathematical backing, here is just one example of a famous paper: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire.
Some of the most well-known of these patterns are:
- Map every element of a collection to a new element (
map)
- Reduce or fold all elements of the collection into a single result value (
fold, foldLeft, foldRight, reduce, reduceLeft, reduceRight)
- Unfold a single seed value into a collection (
unfold, iterate)
As well as special cases of the above, e.g. forall, which checks whether all elements of a collection satisfy a certain predicate is "folding" all elements of the collection into a single boolean value. Or, somewhat harder to see, filter "folds" all elements of the collection into a single value which is in turn a collection of the same type and a subset of the elements. (Yes, the "single result value" of fold can of course be anything, including a collection.)
In fact, it can be shown that fold can implement any iteration, i.e. anything which can be expressed as a loop over a collection, which we know is the same thing as recursing over a collection, can also be expressed using fold.
So, what would it look like to express this in terms of recursion patterns? Unfortunately, I am not very pleased with my result. This is the best I could come up with:
def isBalanced(str: String) =
str.foldLeft((0, true)) {
case ((depth, true ), '(') => (depth + 1, depth >= 0)
case ((depth, true ), ')') => (depth - 1, depth > 0)
case ((depth, true ), _) => (depth, depth >= 0)
case ((_, false), _) => (-1, false)
} == (0, true)
But I feel that I am missing some epiphany. Also, using foldLeft and friends, it is not easily possible to implement the obvious shortcut optimization of stopping processing of the input string as soon as the stack depth is negative, which is trivial to do with imperative loops and with functional recursion.
This solution was suggested in a comment by Tamoghna Chowdhury:
def isBalanced(str: String) =
val depths = str.scanLeft(0) {
case (depth, '(') => depth + 1
case (depth, ')') => depth - 1
case (depth, _) => depth
}
depths.forall(_ >= 0) && depths.last == 0
