Which of these two paren-matching functions is better?

Question

I am currently trying to learn Haskell (after taking a Scala course on Coursera); but while I can write functions that do what I want, I worry that I am not learning to write idomatic/clean/performant code. I am hoping that this is an acceptable place to receive feedback on how I am progressing. Please let me know if my examples are too small/'toy'/not appropriate for this area of the site.

Which of these two parenthesis matching functions is better - or how best should it be written? The function takes a String, and returns True if the parentheses are balanced, otherwise False.

"(hello)()" = True
")(test()" = False
"())" = False

Explicitly written:

balance :: String -> Bool
balance xs = bal 0 xs == 0
 where bal c [] = c
 bal c (x:xs)
 | c < 0 = c
 | x == '(' = bal (c + 1) xs
 | x == ')' = bal (c - 1) xs
 | otherwise = bal c xs

Using foldl:

balance' :: String -> Bool
balance' xs = foldl bal 0 xs == 0
 where bal count char 
 | count < 0 = count
 | char == '(' = count + 1
 | char == ')' = count - 1
 | otherwise = count

I think that the explicitly-recursing one is better since it will terminate early if it detects the String is flawed, but the other one might be 'clearer' since it uses foldl. Both of them happen to be tail-recursive. How would I improve either?

How important is writing tail-recursive functions in Haskell? I have read somewhere that Haskell is very smart about making things tail recursive, but I do not understand enough to understand quite how.

Any help and suggestions would be greatly appreciated, thank you!

Answer 1

I would propose an even less performant solution, but maybe you can improve it...

balance xs = head cumulated == 0 && all (>= 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.

• ony: How about? balance xs = all (>=0) (init cumulated) && last cumulated == 0 ((&&) checks first argument before right one) and cumulated = scanl (+) 0 $ map depth xs (with inverted parenthes). That will not check rest of the string for ")(test()". Btw, you can use foldr since you are using right side.