I've gotten a bit obsessed by functional programming over the last couple of years. I have even seriously thought about writing a book that looks at computational geometry (which is the subject in which I was trained) in the light of functional programming. Most of the standard computational-geometry texts these days approach the writing of code from an imperative standpoint.

I think functional programming is a good way to think about computational geometry for a couple of reasons. First, most problems in computational geometry can be expressed in a purely functional manner. That is, the answers to the problems are usually the same given the same inputs. Secondly, I have bought into the idea that parallel and distributed computing are much easier when state is not being modified. Functional programming forces you to think this way. While many problems in computational geometry are inherently sequential, not all of them are. Using a programming method that allows for the easy addition of more cores seems like a good practice when a problem is encountered that is easily made parallel.

One of the things I have been thinking about as a final chapter for the book that I would like to write is the introduction of monads as a way to "parse" polygons. Monads are commonly used (well, commonly in the functional programming world) to parse strings. They generally scan through with the aid of a stack. There are many algorithms that scan through the points of a polygon with a stack -- the example that I have thought about the most is the visibility polygon.

A visibility polygon is the subset of a polygon that can be "seen" from a point inside the polygon. Here, we regard the segments of the polygon as opaque walls.

The standard algorithm for computing the visibility polygon is not too difficult to implement in an imperative language. In fact, I implemented it already in C++ for the drawing editor ipe. (Though I think that code is now obsolete since the release of ipe 7.)

I've already tipped my hand at how I would think about implementing such an algorithm in a functional language. I would use a variant of a monadic parser to go through the polygon and find the parts that are visible. (That last sentence doesn't give much of a hint about how it's done, but the whole algorithm would take too much space to describe. Suffice it to say that a stack is kept with the "currently visible" portion of the polygon always on the stack.)

I used monads earlier to make a framework for creating and comparing time-series. However, I only used a monad that was already defined by someone else. I think I might need to define a monad on my own this time – a slightly daunting idea. I definitely need to read the rest of Jim Duey's tutorial to make sense of how to do it.