(rough) Grids in Haskell

(This isn’t a full blog post, but a note of a few things about implementing game grids in Haskell).

  • A [[Cell]] structure seems to make sense for a lot of boards. In fact, even the problems I’m looking at might be approached simply indexing into row then col each time you want to access a list. However it feels inelegant, and some of the things I want to do (looking at lines of game pieces in a given direction N/S/E/W) would be more elegant if I can simply traverse the grid in an arbitrary direction.
  • morrow remembered there had been a discussion on haskell-cafe about grids (+ +) recently. It seems to be mainly about infinite grids, but has lots of interesting stuff to absorb.
  • paolino remembered that comonads were useful in grid representation. I don’t understand what they are but google finds http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html which looks interesting.
  • I think I want a zipper, but didn’t know how it would work on [[Cell]]. Saizan clarified: “if Zipper [] a is the zipper for [a], then the one for [[a]] is Zipper [] (Zipper [] a), and depending on which layer you use the next/previous operations you move in one dimension or the other”. This isn’t quite true though, as when you move up/down by rows, you have to somehow remember the columnwise index.
  • (Saizan referred to fmap’ing operations to keep the columns in sync, which is, I think, a more higher-order way of doing the same thing :-)
  • dolio posted an ADT representation of a grid. I don’t understand that at all yet, but it is pretty… He also wrote a Traversable instance (this would appear to be a generic way to expose functions to move around in your arbitrary datastructure)
  • I decided to try to fold a [[Cell]] into a Cell { value=x, down=d, right=r }. This took me several hours last night, during which I cursed my feeble brain, and the fact that mutable references would have made the task trivial in other languages. (However, mutable references would make the grid useless for many useful things, like keeping intermediate copies of grid state). My no-doubt crappy code is on github (I’ll come back to it in more detail later)
  • While I’m whining about haskell being “too hard” I should mention that I’ve got bogged down in representing grids (for games or spreadsheet) in Java, Perl, and Javascript too, so I think it may be more a case of my brain being feeble. That or I’m just overcomplicating things…
  • (As I remember it, the OO representation of grids is simpler to get started with but then I get bogged down with issues of multiple inheritance etc.)

Comments and suggestions welcome, I should write a full post on this soon.