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