Balance Parentheses

Balance.scala

// Missing support libraries
object MissingLibraries {
  case class State[S, +A](run: S => (A, S))  {
    def map[B](f: A => B): State[S, B] =
      State(s => {
        val (a, t) = run(s)
        (f(a), t)
      })

    def flatMap[B](f: A => State[S, B]): State[S, B] =
      State(s => {
        val (a, t) = run(s)
        f(a) run t
      })

    def runAnd(s: S)(p: A => Boolean, q: S => Boolean) = {
      val (a, t) = run(s)
      p(a) && q(t)
    }
  }

  object State {
    def point[S, A](a: => A): State[S, A] =
      State(s => (a, s))
  }

  type Nat =
    List[Unit]

  // forall generalised to State monad.
  // Note that this has the same type as scala.List#forall except:
  //   * State[S, _] appears over every type in return position.
  //   * Implemented as a function, not a method.
  // Note also that we only call flatMap and point, which are methods that appears on more than just State data type.
  def forallState[S, A](a: List[A])(p: A => State[S, Boolean]): State[S, Boolean] =
    a match {
      case Nil => State.point(true)
      case h::t => p(h) flatMap (k => if(k) forallState(t)(p) else State.point(false))
    }
}

object BalanceParens {
  import MissingLibraries._

  def isBalanced(s: List[Char]): Boolean = {
    val z = forallState[Nat, Char](s) {
      case '(' => State(x => (true, () :: x))
      case ')' => State {
        case Nil  => (false, Nil)
        case _::t => (true, t)
      }
      case c   => State.point(true)
    }
    z.runAnd(Nil)(w => w, _.isEmpty)
  }

  def main(args: Array[String]) {    
    /*
    "" : true
    "(" : false
    ")" : false
    "()" : true
    "(())" : true
    "(()" : false
    "())" : false
    "())(" : false
    "(())" : true
    "x" : true
    "(x" : false
    "()x" : true
    "x)" : false
    "x(y(z))" : true
    "x(y)z)(" : false
  */
    val tests = List("", "(", ")", "()", "(())", "(()", "())", "())(", "(())", "x", "(x", "()x", "x)", "x(y(z))", "x(y)z)(")
    tests foreach (x => println("\"" + x + "\" : " + isBalanced(x.toList)))
  }
}

great, thank you!
"(())" runs twice ;-)