Managing state in a Minesweeper clone in Haskell

Question

As a way to learn Haskell I decided to make a Minesweeper clone. I have already written some code and the main structure of the program is ready. It is based on:

• A Board, containing the amount of mines, the list of fields and the width and height of the map.
• A Field, containing the number of adjacent mines or a value indicating that the field is a mine itself. The Field also contains a FieldState (Marked, Hidden or Shown).

The game loop looks like the following:

play board = do
    -- Clear the screen
    putStrLn $ replicate 40 '\n'

    -- Show the board
    print board

    -- Get and process user input
    putStr "Command: "
    -- We are generating a new board to reflect the changes!
    newBoard <- parseInput board <$> getLine

    -- If the game is not ended, go to next step
    if gameEnded newBoard
    then return $ result newBoard
    else play newBoard

This works quite good right now, but I don't like the fact that after each turn I have to generate a new Board. It looks inefficient coming from an imperative language like C++, where you would just need to mutate the existing board.

To the point:

• Is this the correct way to do it?
• Will it be optimized by the compiler?

Answer 1

You're right of course that completely replacing the board is less than optimal, however it's not necessarily as bad as you may think either. If Board uses a [[FieldState]]-2D-grid, then updating a single cell actually re-uses most of the rows (this works without thinking and is perfectly safe, because Haskell is purely functional): for an n × n grid the complexity is O (n), only a constant factor worse than what you need anyway for looking up any given field. It's definitely not going to be any problem whatsoever for a game like Minesweeper.

For something more performance-critical, there are dedicated array types that can do both lookup and updates of single fields (in the IO or ST monad) in O (1). For an application similar to yours, Data.Array.MArray is probably the best fit (though there's a certain trend in the community to rather write your abstractions right around the somewhat lower-level, more optimised vector types).