Re: Solutions and Discussion for Perl Quiz of the Week #23

"John J. Trammell" <[email protected]> writes:

> On Fri, Sep 10, 2004 at 04:49:18PM +0100, Matthew Walton wrote:
>> 
>> Hopefully mine was skipped because the testers didn't have a Haskell 
>> compiler handy (admittedly it's not exactly a standard thing to have 
>> hanging around), because it was *supposed* to follow the specified 
>> invocation format and output.
>
> Well, no, I have a Haskell compiler (thanks, Debian!) but I couldn't get
> your code to run.  Besides, I had 50+ other submissions to worry about.

The problem with his code was that when Matthew Walton posted it to
the mailing list, an extra space was inserted into the source.  Since
haskell is (or at least, is usually) a language where indentation is
significant, this meant it didn't compile.

Find the line that says:

main = do as <- getArgs

In the next line, make sure that "onePerLine" is lined up right
underneath the "as".  (Which means deleting one space)

Then, you can if you want try this variant on his code, which is about
20% faster :).

For either haskell solution, the way to run them is to extract the
mail message into a file whose name ends in ".lhs" and do:

sudo apt-get install ghc6  # Ah Debian...
ghc -O2 -o walton1 walton1.lhs
./walton1 12

And now, my code, which is just his algorithm but done so that the
whole list never need be in memory, taking aggressive advantage of
Haskell's lazy evaluation.

\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] -> [String]
buildvalid _ 0 cs ss = cs:ss
buildvalid 0 n cs ss = buildvalid 1 (n-1) (')':cs) ss
buildvalid o n cs ss = if o >= n
                        then buildvalid (o-1) (n-1) ('(':cs) ss
                        else buildvalid (o-1) (n-1) ('(':cs) $ buildvalid (o+1) (n-1) (')':cs) ss

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

\end{code}