So I got a new book, and I was pretty excited about it: Mazes for Programmers by Jamis Buck (Amazon link).
I figured this would be a good chance for me practice some functional programming -- and then I did it completely wrong.
After reading the first 2 chapters, I was well on my way to creating mazes. I created some using the Binary Tree algorithm:
And some using the Sidewinder algorithm:
It's not hugely exciting so far, but it's a start. And it's nice to have something visual after just a little bit of work.
Very Object-Oriented Code
These mazes weren't created using functional programming, they were created with OO code (which I'll talk about in a bit). The book samples are written in Ruby. Here's the Binary Tree algorithm:
I'm not much of a Ruby programmer, so I did the same thing in C#:
You can grab my code from GitHub if you're interested: jeremybytes: mazes-for-programmers.
So my goal is to get this running with F# because I need to practice to get comfortable with functional programming. I followed the book code in C# because I figured I'd have a better chance of understanding what was going on after I had a working version.
Yes, the code is very object-oriented: there is a Grid class consisting of a set of cells and also knows how to display itself; and there is a Cell class that knows how to link itself to other cells. I figured it was pretty safe to start with the algorithms, though.
If we look at the "Binary Tree" code above, we have a static method that takes a grid as a parameter and returns a grid. It doesn't rely on anything external to itself. This looked like a really good candidate to be converted over to a functional style using F#.
I didn't get very far. In fact, I created a complete mess (that didn't work). I ended up deleting everything I had.
I tried taking the C# code and breaking out bits and pieces into separate functions: the part that get the collection of neighbors of a cell, the part that creates a link based on a random value. The goal was to use these function in a mapping of the entire cell collection.
I wish I had kept the code just so I could show how wrong a direction I was headed.
I'm going to take another shot at this, but I need to understand more of the big picture first. For example, each Cell object knows about all the cells that it's "linked" to. So for example, Look at this picture:
The circled cell object knows that it is linked to 2 other cells: one on the "east" and one on the "south". But more than that, the cell has references to those other 2 cells.
What this means is that by starting with any individual cell object, we can create a graph of the entire maze by walking the links for each cell. This becomes important in Chapter 3 where we start looking for ways to solve a maze using Dijkstra's Algorithm.
Mazes for Programmers intentionally stays away from graph theory. But I think I'm going to have to learn some graph theory if I want to approach this from a more sane direction in the functional world.
Taking the existing objects which are linked to other objects which are linked to other objects... that's going to create a bit of a mess (at least with my current knowledge of these things).
First tries aren't always successful. In fact, they can be a huge learning experience when you discover that you're headed in the wrong direction. When we recognize the wrong direction, we can step back and look at other options.
I'm going to continue coding through the book with C#. This will help me understand the problem space and the solutions. Along the way, I'll start looking into potential functional ways of implementing the code.
Rather than taking the current objects and shoving them into F#, I'm pretty sure there's a better approach. But for that, I'll need to do a bit more learning. Keep an eye out here (and on the GitHub code) to see where I end up.