On Sun, 2007-08-26 at 14:50 +0200, manu wrote:
Hello,
After reading Peter Norvig's take on writing a Sudoku solver (http:// norvig.com/sudoku.html) I decided that I would port his program to Haskell, without changing the algorithm, that'll make a nice exercise I thought and should be fairly easy... Boy, was I wrong !
Anyway, I eventually managed to tiptoe around for loops, mutable state, etc... However, when I run my program against the test data provided (http:// norvig.com/top95.txt), I find it takes around 1m20 s to complete (compiled with -fvia-C and - O2, on a MacBook Pro 2.33GHz Intel Core 2 Duo). That's roughly 8 times longer than Norvig's Python script. That's not what I expected ! My program is also longer than the Python version.
Being a beginner, I am convinced my implementation is super naive and non idiomatic. A seasonned Haskeller would do much shorter and much faster. I don't know how to improve it though !
Should I introduce more strictness ? replace lists with more efficient data structures (ByteStrings, Arrays) ?
Yes. Treating lists like arrays is always a recipe for heartbreak. If you did want to try to match the python code exactly there are mutable arrays and such. http://www.haskell.org/haskellwiki/Sudoku has a bunch of different implementations going for different things.