Brackets, and How to Check that They are in the Right Order

The last exercise I started working on Write Yourself a Scheme was writing a function that reads a string, checks the brackets and returns a Boolean.

It's meant to check the following:

• The brackets open and close in the right order.
• Every bracket that was opened eventually closes.
• Every bracket that is closed has a matching opening bracket that was opened earlier in the list. 

The code for this exercise can be found here.

My first, and simpler, attempt only checks one kind of bracket. I take the string and filter out all the brackets, and work only on those.

checkparents :: String -> (Bool, Int) 

The Int in the tuple is the result of the following formula:

• If the bracket being looked at is an open bracket, +1. 
• If the bracket is a closed bracket, -1. 

The Bool starts at True at the beginning of the list and goes to False if the Int goes below zero or at the end of the list, if the Int does not equal zero. 

This reasoning follows from the fact that if the Int goes below zero, it means that there is a closing bracket that was not opened, as in the case where the first bracket in the list was a closed bracket. Similarly, once we have finished traversing the list, if the Int is more than zero, it means brackets that were opened were not closed. 

I tackled a more complicated version of the same problem with multiple kinds of brackets afterwards.

checkbrackets :: String -> Bool 

The reason why there is no Int is that I hit upon a better way to 'remember' the brackets that had already been 'seen'.

I wrote a helper function of the following type:

pairchecker :: (Char, Char) -> Bool 

This function checks that the first Char is an open bracket, and that the second is it's matching closed bracket. In every other case, it returns False.

Then I wrote a foldr that uses pairchecker and only retains brackets that were either never opened or haven't yet been closed. After the list is traversed, I check if the resulting list is an empty list.

checkbrackets can only be True if the result of the foldr is an empty list. If it's not empty, it means that there were brackets that were either never closed or never opened, and therefore has to be False.