16

I'm starting out with scala, and trying to apply the functional way to it, but I came out with bunch of nested if\else constructions which is hard to read, and I wonder is there nicer way to program such things?

For example I wrote a script, that performs parentheses balancing:

def balance(chars: List[Char]): Boolean = {
    def checkParentesys(chars: List[Char], parentesis: List[Char]): Boolean =
      if (chars.isEmpty && parentesis.isEmpty)
        true
      else
        if (chars.head == '(')
            checkParentesys(chars.tail, '(' :: parentesis)
        else
            if (parentesis.isEmpty)
                false
            else
                checkParentesys(chars.tail, parentesis.tail)

    checkParentesys(chars.filter(s => s == '(' || s == ')'), List())
  }

How can I write it to be more functional and more scala like?

Jason Aller
  • 3,541
  • 28
  • 38
  • 38
Andrey
  • 810
  • 1
  • 9
  • 20
  • 32
    Don't be shy, just say that this question is from scala 's coursera course – AndreasScheinert Sep 21 '12 at 08:06
  • does it makes difference? I've done assignment, in scope of provided material, and wondering for better solution. – Andrey Sep 21 '12 at 08:21
  • 6
    It does make a difference, as you have just violated the Honor Code of coursera by publishing an answer (see https://www.coursera.org/maestro/auth/normal/tos.php#honorcode rule 3) – Frank Sep 21 '12 at 08:58
  • 4
    Frank: Honor Code is nice to follow, but just as Legal Contracts, needs common sense to apply. Intention differentiates the cases. It is in fact expected to seek better ways after solving the solution, isn't it? Do you tell a person wanting knowledge, "Can't say because of the Honor code"? – ron Sep 21 '12 at 09:14
  • 5
    Well, until the first comment is was just a piece of code, without attachment to cource. I think the main purpose of online education as well as traditional, is getting better in stuff, you interested in, not to achive piece of paper without knowledge. But thanks anyway, i didn't consider honor code when i'm posting this question, so i'll be carefull next time – Andrey Sep 21 '12 at 09:19
  • 1
    Yes @pilgrim it's a little odd, I understand that you want feedback and get better. But I feel spoiled now, kind of... – AndreasScheinert Sep 21 '12 at 13:47
  • 1
    @GeorgeStocker: Instead of closing, would it not be better to move this question to codereview? – kiritsuku Sep 21 '12 at 23:01
  • 7
    People, please stop flagging this for violating Coursera's Code of Conduct. That's not up to us to enforce. If it's a good technical question, we don't have a problem with it being here. – Brad Larson Oct 04 '12 at 21:49
  • The code in the question does not work for a test case `"(())(".toList` raising `NoSuchElementException: head of empty list` – franchb May 27 '18 at 18:20

4 Answers4

27

It might be nicer to write it as a fold:

def balance(chars: List[Char]): Boolean = chars.foldLeft(0){
  case (0, ')') => return false
  case (x, ')') => x - 1
  case (x, '(') => x + 1
  case (x, _  ) => x
} == 0
Luigi Plinge
  • 50,650
  • 20
  • 113
  • 180
  • heh) the result is shorter and shorter) thanks, i'm excited to see all those options, looks like functional programming is much more options than imperative programming – Andrey Sep 21 '12 at 05:38
  • 3
    I thought using "return" was bad style? – Ilan Sep 21 '12 at 10:39
  • 2
    Not always. Beginners, especially beginners coming from Java, tend to wildly overuse `return`. But, here `return` is needed to exit early from the fold. There are other ways to solve this, of course (see other answers), but this one seems rather elegant to me, even with the `return`. – Seth Tisue Sep 21 '12 at 15:02
  • @Ilan usually it is, but the standard library doesn't have a fold variant that stops folding when the accumulator hits a condition. Such a method is dead simple to write yourself, but I think `return` is simpler and easier to quickly understand here. – Luigi Plinge Sep 22 '12 at 14:12
19

I don't think there is any reason to filter the list before you traverse it. You can just ignore the non parentheses as you traverse the list. I think it is also unnecessary to build the second list. All you really want to know is that the count of open parenthesis is never negative:

def balance(chars: List[Char]): Boolean = {
  @tailrec
  def _balance(chars: List[Char], count: Int) : Boolean = 
    chars match {
        case Nil => count == 0   // end of the string did we close every open?
        case '(' :: xs => _balance(xs, count+1)  
        case ')' :: xs => (count > 0) && _balance(xs, count-1) 
        case _ => _balance(chars.tail, count) // uninteresting char, skip it
    }

  _balance(chars, 0)
}
stew
  • 11,276
  • 36
  • 49
4

Well:

  1. You could start by writing it with else if conditions.
  2. Go ahead an annotate it with tailrec since it's tail-recursive.
  3. The filter condition can be written more simply as Set('(', ')'), which is a function from Char to Boolean
  4. I think you're missing the condition where chars is empty but parenthesis is not.

So it would look like:

def balance(chars: List[Char]): Boolean = {
  @tailrec
  def checkParentesys(chars: List[Char], parentesis: List[Char]): Boolean =
    if (chars.isEmpty && parentesis.isEmpty)
      true
    else if (chars.head == '(')
      checkParentesys(chars.tail, '(' :: parentesis)
    else if (chars.isEmpty || parentesis.isEmpty)
      false
    else
      checkParentesys(chars.tail, parentesis.tail)

  checkParentesys(chars.filter(Set('(', ')')), List())
}

You could also just turn the whole thing into a pattern match:

def balance(chars: List[Char]): Boolean = {
  @tailrec
  def checkParentesys(chars: List[Char], parentesis: List[Char]): Boolean =
    (chars, parentesis) match {
      case (Nil, Nil) => true
      case ('(' :: charsTail, _) => checkParentesys(charsTail, '(' :: parentesis)
      case (Nil, _) => false
      case (_, Nil) => false
      case (')' :: charsTail, '(' :: parentesisTail) => checkParentesys(charsTail, parentesisTail)
    }
  checkParentesys(chars.filter(Set('(', ')')), List())
}
dhg
  • 52,383
  • 8
  • 123
  • 144
  • Thanks for Set and tailrec. So, there is no way to rewrite the other logic to be more readable. else if doesn't helps much because, in my opinion it confuses to wich if it belongs and breaks logic. I thought i could combine some way multiple checks to one expression? – Andrey Sep 21 '12 at 03:36
  • Yep, thats what i looking for, didn't see you second part of comment – Andrey Sep 21 '12 at 03:38
  • @Pilgrim, I think most programmers of any language would say that the `else if` is *more* readable since it gives the reader a list of conditions. Further, it definitely does *not* break logic; the logic is identical. – dhg Sep 21 '12 at 03:38
  • Ok, maybe you right, anyway, i think that rewritten in pattern matching, it appears more functional, and (instead of unusual syntax for me) it gives clearer logic representation – Andrey Sep 21 '12 at 03:43
3
var parens :List[Char] =  Nil
def matcher(chrs: List[Char]): Boolean = {
     if (chrs.isEmpty) {
        return parens.isEmpty
     }
     else {
         chrs.head match {
           case '(' =>  parens = '(' :: parens ;matcher(chrs.tail)
           case ')' =>  if (parens.isEmpty) return false 
                            else if (parens.apply(0) ==  '(') parens = parens.drop(1) 
                            else return false;  
                            matcher(chrs.tail);
           case _ => matcher(chrs.tail)
         }
     }
}

As you can see I didn't use count because count won't work on ())(

Don
  • 31
  • 2