Parenthesis balancing using Monoid

balance.scala

// From haskell "Monoidal Parsing—Edward Kmett"

import cats.implicits._

final case class Balance(l: Int, r: Int)
object Balance {
  val EMPTY = Balance(0, 0)
  val LEFT = Balance(0, 1)
  val RIGHT = Balance(1, 0)
}

implicit val monoidWeight = new Monoid[Balance] {
  override def empty = Balance.EMPTY
  override def combine(x: Balance, y: Balance): Balance = {
    if (x.r < y.l) Balance(x.l + y.l - x.r, y.r)
    else Balance(x.l, y.r + x.r - y.l)
  }
}

def parse(c: Char): Balance = c match {
  case '(' => Balance.LEFT
  case ')' => Balance.RIGHT
  case _ => Balance.EMPTY
}

def balanced(x: String) = x.toCharArray.toList.foldMap(parse) == Balance.EMPTY

println(balanced("(())()")) // true