WordLadders in Haskell

Over the weekend I wrote my first Haskell program. It’s called WordLadders and I’ve spent a total of about 5.5 hours on it.

I’ve been interested in functional programing for quite a while. Last year I started reading about Haskell more heavily, including all of Learn You a Haskell and Real World Haskell. I’d been trying to find a small program that I thought I could actually make on my first try, but I hadn’t come up with any really good answers.

Then on Friday Nathan Smith posted I wrote a Go program for solving “doublets” (AKA word ladders) using A* search algorithm on /r/golang. It uses a dictionary and the A* algorithm to try to connect two words through a list of real words, changing only one letter at a time. So if you entered “goat” and “toad”, the path might be goat -> goad -> toad.

Well that seemed simple enough to me. There are only four parts to the program:

  1. Reading in the dictionary file
  2. Creating a graph that links the words together
  3. Finding the shortest path between two words with A*
  4. Handling user IO (getting words, showing answers)

That’s the order I ended up writing the program in. Haskell has a reputation that “If the code compiles, it works (almost all the time)“, and that was my experience. My program contained only a single bug that the compiler didn’t find. When doing recursion within my A* implementation I was forgetting to remove the node I just processed from the open set, leading to an infinite loop. There’s no way for the compiler to catch that, but it caught everything else.

The actual process of writing the program was a little rough. I use IntelliJ all day at work and wanted to continue to use it, but the Haskell plugin doesn’t work right now. Development just picked back up after a two year hiatus and the old plugin doesn’t work with my (much newer) version of IntellJ. In the end I ended up using TextWrangler with a simple syntax highlighter and the ghci REPL.

My program works correctly as far as I can tell. It can find the longest word ladder (between ‘charge’ and ‘comedo’) in 8.5s on my 2010 MacBook Pro. It also correctly handles words that can’t be linked (such as ‘apples’ and ‘spoons’).

I’ve posted it to /r/haskell to get some advice on improving my program. There are a few things that I felt I stumbled on. There were also some issues I didn’t fully understand, but as often happens the solutions came to me while I was writing out the questions. Rubber duck debugging strikes again.