[Haskell-cafe] Help understanding Haskell runtime costs

[Henning Thielemann]

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.