[Haskell-cafe] Algorithm for labeling same-colored regions in a 2D array?

[Steve Trout]

(Apparently joining the list through the Google Groups interface doesn't
work, but the post still shows up there. Sorry if you see this twice!)

For fun, I'm writing a rules engine for the board game Go (in Haskell
obviously). I have a board, which is a grid of spaces that can contain a
black piece, a white piece, or nothing. Part of what i need to do is to
detect regions of the same "color" (black, white, or empty) and get
information about them like their size, the color of the bordering spaces,
etc. Regions are bounded by other colors or the board edges in cardinal
directions. I'm just starting on this so I haven't picked my data
structures yet, but Vector (Vector _) or Map (Int, Int) _ are what I've
toyed with.

I have a vague idea of how I would go about this in an imperative language
with mutation. I'd iterate over the board, keeping lists of points
contained in the same region, combining (relabeling) regions if they happen
to connect later on. (I realize there are probably better algorithms in
those languages, but that would be my first attempt.) I know i could cobble
something like this together in the State monad, but I have a feeling that
there ought to be a better (more "Haskellish"/pure-functional) way.

What would a Haskellish algorithm for this kind of thing look like? I
wouldn't mind a complete answer or just a nudge in the right direction.

Thanks,
-Steve
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140630/81d71903/attachment.html>