Codewars - Parentheses

The Codewars Valid Parentheses challenge is to evaluate a string containing parentheses, returning true if they are properly balanced and false if they aren't. Nice fit to feel how beginner level Haskell compares to intermediate Python.

Here there be spoilers.


My solution was simple: iterate over every characater in the string, keeping track of how many parentheses are open. If it drops below 0, return False. At the end, they are valid if the count is exactly 0.

I tried it in Haskell first.

-- | Returns true if a given string contains only balanced parenthesis
validParentheses::String -> Bool
validParentheses xs = vp 0 xs

-- | Helper function for validParenthesis
vp::Int -> String -> Bool
vp i (x:xs)
  | i < 0 = False

vp i "" = i == 0
vp i ('(':xs) = vp (i + 1) xs
vp i (')':xs) = vp (i - 1) xs

This one wasn't too hard: the structure is very similar to one I learned through an EDx class on program design. The test cases did not include characters other than the open and close parenthesis.

Codewars allows you to see other's solutions, which is a nice feature for someone looking to improve their work.

One I liked better than mine uses a case structure for matching the parentheses, and used the empty string as the first base case.

validParentheses :: String -> Bool
validParentheses s = parse s 0

parse :: String -> Int -> Bool
parse [] n = n == 0
parse (x:xs) n
  | n < 0 = False
  | otherwise = case x of
                  '(' -> parse xs (n + 1)
                  ')' -> parse xs (n - 1)

Another simply incorporated the helper function into a where clause of the primary function, and named it "go."

validParentheses :: String -> Bool
validParentheses = go 0
    go n ('(':xs) = go (n+1) xs
    go n (')':xs) = n > 0 && go (n-1) xs
    go n []       = n == 0

I'm not sure if that's a common practice. It seems common to need a light wrapper around a single, implementation-specific helper when working with functional languages. Standardizing around a single name for that case feels appropriate.


After determining the algorithm, writing a solution in Python was almost too easy.

def valid_parentheses(string):
    v = 0
    for x in string:
        if x == '(':
            v += 1

        if x == ')':
            v -= 1

        if v < 0:
            return False

    return v == 0

The variation I liked was very similar:

def valid_parentheses(string):
    cnt = 0
    for char in string:
        if char == '(': cnt += 1
        if char == ')': cnt -= 1
        if cnt < 0: return False
    return True if cnt == 0 else False

The one-line if-statements are an easier read, and using 'cnt' as a variable name seems clearer. I'd keep my own take on the return statement though.

Experiential comparison

I found it much easier to write Python. Some of that is that I've been at it for longer, but the syntax, lack of typing, and the ability to just use a counter variable instead of writing a helper all mean there is less to track.

Nevertheless, I'm still drawn to Haskell and functional programming. I suspect that getting used to the patterns that replace counters and similar variables comes with practice, and I'm strongly inclined to believe that disciplined typing makes for fewer run-time errors. I also suspect that coding better in Haskell could lead to coding better in Python - discipline of thought has more to do with the quality of any given piece of software than laguage choice.