[SPOILER] Solution to QOTW #23 in Haskell

I've not done my Perl solution yet... this seemed like a problem so 
elegant to express in Haskell, although it turned out that the most 
obvious solution was incredibly slow. I'll explain how I did it in 
Haskell, in case anyone's interested, and I may do a Perl solution over 
the weekend, although I imagine that territory will be well-covered by 
others. Again, I hope nobody minds that I'm not submitting in Perl to a 
Perl quiz...

The obvious solution was to generate all possible combinations of '(' 
and ')' at the length required, then filter that list to find all the 
ones which match. Simple enough, but of course you do a lot of 
unnecessary generation and checking along the way. Lazy evaluation 
mitigates the cost a little, but not much as you ultimately still have 
to evaluate the entire set of possible strings. Which is extremely large.

Thus a fairly common trick for speeding up a Haskell program - combining 
generation and filtering. A function that discards invalid strings as 
they're being generated is significantly faster, and then I came across 
a function which is only capable of generating valid strings, which is 
fastest of all. That's the one presented here.

This email is presented in the LaTeX-like literal Haskell format, so you 
can save the thing to a .lhs file and throw it at GHC and it should just 
work.

The function that does all the work is 'buildvalid':

\begin{code}

module Main where

import System

-- constructs a list of Strings containing all possible
-- valid progressions
-- builds the strings backwards as it's more efficient to
-- prepend than append to a normal list
buildvalid :: Int -> Int -> String -> [String]
buildvalid _ 0 cs = [cs]
buildvalid 0 n cs = buildvalid 1 (n-1) ('(':cs)
buildvalid o n cs = if o >= n
                     then (buildvalid (o-1) (n-1) (')':cs))
                     else (buildvalid (o-1) (n-1) (')':cs))
                          ++ (buildvalid (o+1) (n-1) ('(':cs))

\end{code}

buildvalid takes two integers and a string (which is just a list of 
characters). The first integer is the number of open pairs at the 
current position, giving an idea of how many close parentheses are 
needed to make sure the string is valid. The second is the number of 
characters left to go in constructing the string. The string is the 
string constructed so far. The function has three alternative forms.

If there are no characters left to go, simply return a list containing 
the string so far. This is the case which finishes the recursion.

If there are no open parentheses, call buildvalid recursively with one 
open pair, one less character to go and the string so far with '(' 
prepended.

In all other cases, if there are only enough characters left to close 
the existing open pairs, call ourselves recursively with counters 
decremented appropriately and a ')' prepended, otherwise call ourselves 
with '(' and with ')' and join the resulting lists together, thus 
covering all possibilities from this point.

We build up the strings backwards because Haskell's lists are much more 
efficient if you prepend - appending is O(N) on the size of the list.

Note also that buildvalid doesn't work well on numbers which aren't 
multiples of two. The functions which use it have to make sure nobody 
passes a bad number in.

This function is obviously not very friendly, so we wrap it in another one:

\begin{code}

fcombs :: Int -> [String]
fcombs n = map reverse $ buildvalid 0 (2*n) ""

\end{code}

This function calls buildvalid with an appropriate set of starting 
parameters. This produces a list of backwards strings, so the standard 
function 'map' is used to apply 'reverse' to every element of the list 
which buildvalid produces, thus giving us a list of strings suitable for 
display.

\begin{code}

onePerLine :: [String] -> IO ()
onePerLine xs = putStr $ foldr (\x y -> x ++ "\n" ++ y) "" xs

main :: IO ()
main = do as <- getArgs
           onePerLine $ fcombs $ read (head as)

\end{code}

These two functions handle display and invocation. onePerLine uses a 
folding function to take the list of strings and replace all its 
constructor functions with a function that appends two strings with a 
newline in the middle. The resulting string is then printed to the 
standard output.

main is the function invoked by the runtime system when the program is 
run. It binds the command line arguments (as a list of strings) to the 
name 'as', then uses 'read' to convert the first argument to an integer, 
which is passed to 'fcombs' to generate the list of matched strings, 
then that is passed to 'onePerLine' for display. An alternative body for 
main replaces the second line with

print $ show $ length $ fcombs $ read (head as)

Which just prints the length of the produced list. This cuts a 
substantial amount of time off the program's execution.

Execution times on a 1GHz Apple PowerBook G4 with 768MB of RAM running 
Mac OS X 10.3.5, with the Glasgow Haskell Compiler 6.0.1 as the 
compiler, are as follows:

parens 12:
real    0m28.512s
user    0m3.770s
sys     0m1.430s

parens 10:
real    0m2.549s
user    0m0.400s
sys     0m0.130s

parens 12 > /dev/null:
real    0m3.115s
user    0m2.650s
sys     0m0.170s

parens-noprint 12:
real    0m1.502s
user    0m1.190s
sys     0m0.100s

parens-noprint is the version compiled without the onePerLine display 
code call, thus avoiding having to construct a list out of a list of 
200,000-odd elements, which is bound to be expensive.


A possible performance enhancement is to use a Snoc list instead of a 
normal Cons list. Snoc lists are just backward lists - they're faster 
appending than prepending. Potentially this would avoid having to 
reverse all the produced lists for display, but I'm not sure how 
expensive it is to display a Snoc list over a normal list - it may work 
out the same as calling reverse and then printing a normal list. Might 
be worth a try though.