Which of these two paren-matching functions is better?
I would propose an even less performant solution, but maybe you can improve it...

balance xs = head cumulated == 0 &amp;&amp; all (&gt;= 0) cumulated where
  cumulated = scanr (+) 0 $ map depth xs
  depth '(' = -1 
  depth ')' = 1
  depth _ = 0


Note that I work "backwards" (scanr and inverted parens values) in order to avoid a call to last cumulated.