manu
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
Your program was wrapped by your mail client, so you may want to hpaste your program for easier digestion.
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 !
Disclaimer: I'm not an experienced Haskeller either, and I haven't had a real look at your code at all. The following is only what stroke me by a quick look. Gurus may eventually reduce your code into a thirty-line version that also runs quickly.
-- Types type Digit = Char type Square = String type Unit = [Square]
-- We represent our grid as a Map type Grid = M.Map Square [Digit]
Your profiling output suggests that much time is consumed by the lookup function. Since you're using (fromJust . lookup) everywhere anyway, a data structure not envolving the Maybe type is probably a more succint choice. And why bother with characters and strings? So I propose type Square = (Int,Int) type Grid = Array Square Int -- or [Int], if the algorithm requires that Where the array's bound are (0,0), (8,8) or (1,1), (9,9), according to your taste.
newV2 <- case length newCell of 0 -> Nothing 1 -> do let peersOfS = [ s' | s' <- lookup s peers ] res <- foldM eliminate newV (zip peersOfS (cycle newCell)) return res _ -> return newV
The use of “length” here is not an actual performance problem, but unnecessary. Simply write: case newCell of [] -> ... [_] -> ... _ -> ... The same is valid for your other use of length. Malte