I'm trying to implement a function in Haskell that returns a list containing all possible moves for the player who's up. The function's only argument is a String composed of an actual state of the board (in Forsyth-Edwards Notation ) followed by the moving player(b/w).
Notation example : rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w (starting board state)
A move is transmitted as a string of the form [origin]-[destination]. The destination is always a position of the form [column][row], where the lower left square is called a1 and the upper right square is called h8. A move would be for example the move "b3-c4". (no castling/En-passant).
In Java I would use a 2d Array for the Board, but in Haskell I can't find a similar solution (I'm new to functional programming).
What would be a good way/data structure to represent the chess board in?
There are two primary options for storing a board state. The first is a 2D list of Maybe, where a piece would be represented as, e.g. Just $ Piece Black King and a blank square would be represented as Nothing. This optimizes determining if a square is occupied over listing where pieces are (which might be important if you plan to add rendering later):
type Board = Vector (Vector (Maybe Piece))
data Piece = Piece { color :: Color
, type :: PieceType }
The second option is to store a list of pieces and their locations. This implementation is faster to enumerate the locations of all pieces, but slower to check if there is a piece on a particular square:
type Pieces = [Placement]
type Placement = { position :: Position
, piece :: Piece }
data Position =
Pos { rank :: Int
, file :: Int }
deriving (Show, Eq)
data Piece =
Piece { color :: Color
, ptype :: PieceType }
deriving Show
EDIT: It's worth noting that with an 8x8 grid and a maximum of 32 pieces on the board, the performance hit either way is going to be minimal unless you're doing a lot of calculations.