Re: [SPOILER] Solution to QOTW #23 in Haskell

Matthew Walton <[email protected]> writes:

> 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...

I looked at your Haskell solution, and something occurred to me:

If you're going to build the strings backwards - and this is Haskell,
so you're going to do that - why not just build the final output
backwards to begin with, and skip the reverse stage?

I will also confess to not really having gotten the meaning of foldr
and related functions, (that's probably because I am not actually a
Haskell programmer, but just play one from time to time) so I
eliminated them in favor of a function whose use I could understand.

I think that the end result is easier to read, at least for this
non-Haskell programmer.  (You'd just have to explain the meaning of
mapM_)

\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))

main :: IO ()
main = do as <- getArgs
          mapM_ putStr $ buildvalid 0 (2*(read (head as))) "\n"

\end{code}

The result is slightly faster.  However, it still can't hold a candle
to the C-language version posted here by Bruce Keeler, but that's to
be expected, I guess.  Perhaps with more efficient 

I timed them on 14 pairs since I needed to go that long to eliminate
the noise on my system:

cush:~/hackery/perl-qotw/qotw23$ time ./hs-parens 14 > /dev/null

real    0m20.094s
user    0m18.680s
sys     0m0.074s
cush:~/hackery/perl-qotw/qotw23$ time ./hs-parens1 14 > /dev/null

real    0m16.715s
user    0m15.545s
sys     0m0.046s
cush:~/hackery/perl-qotw/qotw23$ time ./bruceparen3 14 > /dev/null

real    0m2.289s
user    0m0.683s
sys     0m1.459s

So then, thinking about the difference between the haskell language
version and the C-language one, I wondered if it would be worth it to
change the signature of buildvalid to:

buildvalid :: Int -> Int -> String -> IO ()

and never go through the list ++.  However, the resulting change only
knocked about 1.7 seconds off the time for 14 pairs.

I think it's worth noting that the improved haskell version does beat
both my optimized perl version and MJD's regexp fancy footwork.
(Though the original haskell version does not)