Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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. –  ony Dec 12 '12 at 21:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.