Some time ago, I read this blog post, “Clojure & Python, Side by Side” and thought that it would be a good practice to port the Sudoku(1) solver to Haskell for improving my Haskell knowledge. First I read Peter Norvig’s original post(2)  and understood his algorithm to solve a Sudoku puzzle. My first guesstimation was that it would take four or five hours at most in total since I was going to port the approach as it is without introducing any special tweaks for Haskell or whatever. But… it took more than 24 hours in total in the end.

  • Haskell code (warning: I’m a veritable novice in Haskell.)

Anyway, you can see my shabby result here:

https://gist.github.com/948338#file_sudoku.hs

  • Result

The original Python code was 214 lines. My Haskell one is 276 lines. Not bad considering the original solution by Mr. Norvig was very decent.

Next, a simple performance comparison. As you can see below, my Haskell one is a little slower than the Python one. Again, not too shabby as a first try.

  • What I’ve learned
    • Mr. Novig’s Sudoku solver algorithm is, probably not the best one out there, but still worth learning(2).
    • His Python solution seems beautiful to me. (Again, I’m not a Python expert.)
    • The fact that both Python and Haskell supports almost an identical form of list comprehension(3) was very useful.
    • The absence of assignable variables in this pure functional language, Haskell was not as big a difference as I had first expected.
    • If there were no Hoogle(http://haskell.org/hoogle/) and Google, I wouldn’t have made it even with a few days.
    • The fact that there is neither iteration nor early-exit in that, which are so natural in ever-familiar C-style languages, gave me a hard time in porting.
    • One should think in recursion instead of iteration in the functional world.
    • Even better, one should think in fold and monad(5).
    • Haskell has many kinds of folds: foldl, foldr, foldl’  and foldr’, which added more confusion to my beginner brain(4).
    • The good thing was that the infamously recondite concept of monad(5) has become a little bit clearer. Without it, in the functional world, I noticed that too-deeply-nested case statements naturally occur.
    • Even though Haskell supports very powerful type inference, it’s beneficial for programmer’s understanding to declare function types explicitly.
    • As there is a saying, it was true that it works out of hand once it’s compiled successfully in Haskell. Although it wasn’t an easy thing for me to make it compiled properly…
    • Haskell provides a special ‘do’ syntax in the IO monad to support IO in a purely functional world. The problem was that it felt like a totally different language from other pure parts of Haskell.
    • A unique point of Haskell, laziness, also caused some headaches. (As you can see in my code, I had to force a strict evaluation to get a result in some situation.)
  • Conclusion
    • Haskell is a totally different beast from imperative languages.
    • Having read one Haskell book (in my case, “Real World Haskell”(9)) didn’t make me even a novice programmer in Haskell. (Not like the time when I learned Python)
    • My code is surely far from ideal, even within the same constraint that directly ports Mr. Norvig’s approach. Without that constraint, there are many other interesting ways to solve a Sudoku in Haskell, of course(10).
    • Even though it took much longer than expected, it was a very valuable experience. :)