Help with a Shootout program

Carsten Schultz carsten at
Thu Feb 24 09:46:37 EST 2005

Hi Alson!

On Thu, Feb 24, 2005 at 07:40:49AM -0500, Alson Kemp wrote:
> All,
> 	In order to teach myself Haskell, I've been tinkering with some of
> the Shootout ( programs.

Good idea.

> Substantially improved the Mandelbrot program.  Then started to work
> on the Spellcheck program, since Haskell seemed to do quite poorly
> at it.

Welcome to the club :-)

> Original program: 
>  import Data.Set
>  main = do
>   d <- readFile "Usr.Dict.Words"
>   let misspelled x = not $ x `elementOf` (mkSet (lines d))
>   interact $ unlines . filter misspelled . Lines
> The original program is nice and short, but uses Set to hold the
> 80,000 word dictionary.  The Input file is 80,000 words, too, so I
> figured that searching the Set dictionary would be an O(n^2) task
> (80,000 spellchecks x linear search on 80,000 word dictionary Set).

It's O(n*log n), since a lookup in Data.Set is O(log n).

The O(n^2) version would be

main = do
   d <- readFile "Usr.Dict.Words"
   interact $ unlines . filter (not . (`elem` (lines d))) . Lines


The real performance problem propbably is not O(n) vs. O(n*log n) but
slow String operations in general.  After all, String is a lazy list
of Char.  Have a look at the thread mentioned above, possibly Simon's
version has become fast again, otherwise it would be an opportuniy to
reconsider the problems mentioned there.

Take care,


Carsten Schultz (2:38, 33:47)
PGP/GPG key on the key servers, 
fingerprint on my home page.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url :

More information about the Glasgow-haskell-users mailing list