[Haskell-cafe] ACM Task for C++ and Java programmers in Haskell. How to make code faster?

[Vasyl Pasternak]

Hi!

Recently I've found interesting ACM research on C++ and Java efficiency.
This task also was been solved on lisp/scheme and is described on
http://www.flownet.com/ron/papers/lisp-java/

I tried to solve this task on Haskell but stuck with efficiency
problems (approx in 1000 times slower and takes 20 times more memory).
I hope
the approach, I've used is correct and problem with data structures
and implementation. It took more than 81% of time for garbage
collection. I tried to use ByteStrings instead of Strings, but
unfortunately it didn't help.

The entire code I placed on http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2764

The original instructions are on:
http://www.flownet.com/ron/papers/lisp-java/instructions.html

Dictionary file could be downloaded from:
http://www.flownet.com/ron/papers/lisp-java/dictionary.

Input data: http://www.flownet.com/ron/papers/lisp-java/input.txt

Expected output: http://www.flownet.com/ron/papers/lisp-java/output.txt

Could someone help me to make this code faster? I'd like to see
solution that will be elegant and fast, without heavy optimizations,
that will make code unreadable. Also, if it possible, prepare the
program to support SMP parallelism.

Very thanks in advance. Hope you'll enjoy this task :)

-- 
Best regards,
Vasyl Pasternak