2
\$\begingroup\$

I was working on the problem to check if the parenthesis are balanced using Scala.

Examples:

  • balance("(Hello (my) name is (StackOverflow))") -> True
  • balance("(Hello (my) name is StackOverflow))(((((((") -> False

The following implementation is working, however I'm wondering: What would you suggest to change in this implementation to make it more functional?

In particular I don't like the use of try-catch in this solution.

  import scala.collection.mutable.Stack

  val OPEN_PARENTHESIS: Char = '('
  val CLOSED_PARENTHESIS: Char = ')'

  def balance(chars: List[Char]): Boolean =
    val parentheses = chars.filter(char => char == OPEN_PARENTHESIS || char == CLOSED_PARENTHESIS)
    val emptyStack = Stack[Char]()
    isBalanced(parentheses, emptyStack)

  private def isBalanced(chars: List[Char], stack: Stack[Char]): Boolean = chars match
    case Nil => stack.isEmpty
    case x :: xs =>
      try {
        val nextStack = processChar(x, stack)
        isBalanced(xs, nextStack)
      } catch {
        case e: Exception => false
      }

  private def processChar(char: Char, stack: Stack[Char]): Stack[Char] = char match
    case char if char == OPEN_PARENTHESIS => stack.push(char)
    case char if char == CLOSED_PARENTHESIS => stack.tail
    case _ => throw new IllegalArgumentException("The given char is not valid")
```
\$\endgroup\$
4
\$\begingroup\$

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.

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.

\$\endgroup\$
3
  • \$\begingroup\$ I humbly volunteer: def isBalanced2(str: String) = { val depths = str.scanLeft(0) { case (depth, '(') => depth + 1 case (depth, ')') => depth - 1 case (depth, _) => depth } depths.forall(_ >= 0) && depths.last == 0 } Sure, this appears to iterate over the string twice, but it does half the work for each iteration, so should be equivalent in performance (minus intermediate list creation) to your idea. Functional elegance and performance are not often compatible anyway ;P \$\endgroup\$ Jan 10 at 14:41
  • \$\begingroup\$ Sorry for the crap formatting in a comment - This should be better \$\endgroup\$ Jan 10 at 14:44
  • \$\begingroup\$ Nice use of scan. \$\endgroup\$ Jan 10 at 16:27
5
\$\begingroup\$

First off, I'm not sure why processChar throws an IllegalArgumentException on non-paren characters - wouldn't it be fine to just ignore those characters instead and return the stack unchanged? Those characters don't affect whether a string is balanced or not, after all.

And if we don't mind passing over non-paren characters, well, there doesn't seem to be much reason to remove them in balance before calling isBalanced, right?

I also find those guards a bit strange, though admittedly I don't know Scala very well. If it's possible to pattern match on OPEN_PARENTHESIS and CLOSE_PARENTHESIS directly instead of using pattern guards like case OPEN_PARENTHESIS => stack.push(char), I feel like that would be just a bit cleaner, at least for situations like this with a small number of cases. If there were multiple sets of brackets (like if we were not just matching ( to ) but also [ to ], say), guards probably would be the way to go

But if you're only matching on one type of bracket, using a stack feels a bit overkill - the only information you're using is how many characters are on there, so we could just cut out the middleman and keep an Int that counts how many unmatched open parentheses we've seen. That would also avoid throwing exceptions as a result of trying to pop from an empty stack - for example, you could do something vaguely like

private def isBalanced(chars: List[Char], unmatched: Int): Boolean = chars match
    case Nil => unmatched == 0
    case '(' :: xs => isBalanced(xs, unmatched + 1)
    case ')' :: xs => (unmatched > 0) && isBalanced(xs, unmatched - 1)
    case _ :: xs => isBalanced(xs, unmatched)

Though if you do want to use a stack, I believe you should be able to get similar results by checking for ! stack.isEmpty instead of unmatched > 0 in the close-paren case

\$\endgroup\$
1
  • 1
    \$\begingroup\$ If you change List[Char] to Seq[Char], and give the unmatched: Int a default value, that will achieve the interface that the OP wants, as can be seen here. \$\endgroup\$
    – jwvh
    Jun 15 '21 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.