[Haskell-cafe] Help understanding Haskell runtime costs
schlepptop at henning-thielemann.de
Thu Aug 11 18:23:58 CEST 2011
On 09.08.2011 01:43, Thiago Negri wrote:
> Hello all,
> I'm relatively new to Haskell and trying to solve some online judge's
> problems in it.
> One of the problems is to say if a given sentence is a tautogram or not.
> A tautogram is just a sentence with all the words starting with the same letter.
> My first try (solution is ok) was to do it as haskeller as possible,
> trying to overcome my imperative mind.
> But it did bad at performance (0.30 secs of runtime, 4.6 mb of memory):
> -- code start
> import Data.Char (toLower)
> main = getContents>>= mapM_ (putStrLn . toStr . isTautogram . words)
> . takeWhile (/= "*") . lines
That's still imperative! :-)
How about 'interact' and using 'unlines' instead of 'putStrLn' ?
> toStr :: Bool -> [Char]
You may want to write String instead of [Char] for clarity.
> toStr True = "Y"
> toStr False = "N"
> isTautogram :: [[Char]] -> Bool
> isTautogram (x:) = True
I assume this case is not necessary, since all  == True anyway.
> isTautogram (x:xs) = all ((== firstChar) . toLower . head) xs
> where firstChar = toLower . head $ x
It is maybe more elegant, not to compare all words with the first one,
but to compare adjacent words in the list:
all (zipWith (...) xs (drop 1 xs))
> Note that the only thing that changed between the two tries was the main-loop.
> The second version runs faster (got 0.11 secs) and with less memory (3.6 mb)
> Can someone explain to me what is really going on?
> Maybe pointing out how I can achieve these optimizations using
> profiling information...
Interesting observation. I do not see a problem quickly.
More information about the Haskell-Cafe