Parenthesis balancing using Monoid
// 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