Scala function fails when changing return type from Unit to String-CodePudding

I a teaching myself Scala, and have been dealing with the algorithmic problem of finding all balanced pairs of n parenthesis.

So, the following solution works:

object GetAllValidParenthesis extends App {
  def generateParenthesis(n: Int): Unit = {

    parenthesis("", 0, 0, n)

  }
  
  private def parenthesis(output: String, open: Int, close: Int, pairs: Int): Unit = {
    if ((open == pairs) && (close == pairs)) {
      println(output)
    }
    else {
      if (open < pairs) parenthesis(output   "(", open   1, close, pairs)
      if (open > close) parenthesis(output   ")", open, close   1, pairs)
    }
  }

  println(generateParenthesis(3))
}

But, if I wanted to return a String instead of Unit (so as to later keep all strings in some data structure, like an array buffer), i.e., I did this:

private def parenthesis(output: String, open: Int, close: Int, pairs: Int): String = {
    if ((open == pairs) && (close == pairs)) {
      output
    }
    else {
      if (open < pairs) parenthesis(output   "(", open   1, close, pairs)
      if (open > close) parenthesis(output   ")", open, close   1, pairs)
    }
  }

The compiler tells me:

type mismatch;
 found   : Unit
 required: String
      if (open > close) parenthesis(output   ")", open, close   1, pairs)

But it is impossible for the function to return anything but a String, since the only "return" is in the line that says "output", the rest are recursive calls.

Why does this happen? Is there any way in which I could fix this?

Thanks in advance for your help.

CodePudding user response：

In Scala, every expression has a value.

That's to say


// this is not a Boolean value
val exp = if (2 > 1) true

// in fact, is the same as following. The `Unit` and `Boolean`'s common type is `AnyVal`
val exp: AnyVal = if (2 > 1) true else {}

In your problem, your function should generate a string of parenthesis and append it to result set rather than just return the value.

I have just write solution of this problem.

May be it's more appropriate like following

import scala.collection.mutable.ArrayBuffer

object GenerateParenthesis {

  def generateParenthesis(n: Int): List[String] = {

    val res = ArrayBuffer.empty[String]

    def travel(l: Int, r: Int, curString: String): Unit = {
      if (l == 0 && r == 0) res  = curString
      if (l > 0) travel(l - 1, r, curString   "(")
      if (r > l) travel(l, r - 1, curString   ")")
    }

    travel(n, n, "")
    res.toList
  }
}

The test code can be found here:

https://github.com/counter2015/LeetCodeScala/blob/6a3ff3d28a7b378490105684d080418c287680d8/src/test/scala/algorithms/medium/implementation/GenerateParenthesisTest.scala