Wednesday, March 15, 2017

Approaching Functional Programming Completely Wrong

 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.

Making Mazes
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.

Functionally Challenged
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.

Trying Again
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).

Continuing
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.

Happy Coding!

7 comments:

  1. To just draw a maze using that generation algorithm, my first jottings are here -- https://gist.github.com/SteveGilham/ca75810bb7b588905c80e4d1dfc26931

    It includes the special cases of the top row (no northern neighbours) and right-hand column (no eastern neighbours) somewhat more explicitly than the OO/imperative starting point does.

    ReplyDelete
    Replies
    1. Thanks, Steve. I appreciate the example. This will be great for me to dig through and help me think about the problem differently.

      Delete
    2. You're welcome. Puzzles like this are fun.

      It's comparatively simple to augment the previous example so that each cell knows whether it can be entered from the south or the west (and draw " ", "< ", " V " or "<V " in each cell as appropriate) locally by brute force, and with a little more thought, it turns out to be simpler to do so by taking advantage of the "grain" of the algorithm and growing a tree structure incrementally from the SW corner that ends up rooted in the NE cell (https://gist.github.com/SteveGilham/299e0561c2ac0586fc35485e81989be6). I'm pretty certain that direct linking in the opposite direction as well can't be done immutably, but a separate immutable data-structure can be built to map cells to their exits (extend the Connected type with a self-coordinate pair initialised by accumulation, build a pair to node map, then for each node compute exit coordinate and build a node to exit node map), which then between them allow us to traverse arbitrary paths.

      Delete
    3. The westward runs in the sidewinder maze make growing a tree in that case rather more complicated. That was a fun problem to solve given the constraints of immutability and being able to draw appropriate arrows from "<V>" in each cell as appropriate, based on a linked tree structure. There's a gist for that too.

      Delete
  2. I feel like I'd be helping if I pointed you in the direction of the ‘fgl’ library for Haskell as an example of how to work with graphs in a functional way, and comonads (especially the ‘store’ comonad) for the case where you have a ‘position’ and want to do things with your local ‘environment’.
    That's kind of a deep end to jump into, though, so maybe it would hinder more than help to try that at this point. Who knows.

    ReplyDelete
    Replies
    1. Thanks, James. You're right; this is probably a bit deep for me at the moment, but it may be useful once I dig in a bit more. I appreciate the help.

      Delete
  3. A completely worthwhile video on the functional design of a board game (possible) vs OOD (nigh impossible)
    https://m.youtube.com/watch?v=Tb823aqgX_0

    How OOP may be relevant
    https://www.quora.com/What-differentiates-a-programmer-and-a-really-good-programmer-How-are-the-codes-being-considered-as-good-or-bad/answer/Christian-Baune

    ReplyDelete