Basic logic

[yallop]

Implementation of basic game logic.

I spent a while trying out various ways to represent the game state, but decided in the end to stick with a simple representation for pedagogic purposes. The representation in this request is probably the first thing you'd think of:

• a tile is an int
• a square is a tile option
• a row is a square list
• a board is a row list

This makes defining the basic game logic very straightforward, with plenty of nice algebraic properties (e.g. shift R = rev ∘ shift L ∘ rev), and opens up the possibility of improving the representation as an exercise. Some possible improvements in that vein:

• changing tile to a variant type
• using arrays instead of lists
• retaining knowledge of where the empty squares are
• using a type that enforces a rectangular board (no ragged rows)
• using a type that enforces a square board

One drawback of the simple representation is the GUI-unfriendliness, since operations (such as shift and insert_into_board) return fresh boards, albeit with some shared structure. It might be easier to work with on the GUI side if the various operations instead returned a list of transformations to be performed, but calculating the transformations is sufficiently straightforward as to make that approach seem quite artificial: nothing is gained by separating the code that calculates the transformations from the code that perform them. Furthermore, it seems tricky to find a representation of transformations that makes much sense without an accompanying board configuration, so splitting things up makes the types significantly looser.

As mentioned above, there are two operations on boards:

val shift : move -> board -> board
val insert_into_board : square -> board -> board option

where move is one of the four available directions, and insert_into_board fails if there are no empty squares. Implementing these should provide plenty of fun: it involves (exhaustive) reasoning by cases, higher-order functions, pattern matching and algebraic/wholemeal thinking. Together with the optional extensions above, we should have enough to while away a few hours.

There are some basic tests, defined using qcheck. We should improve this set to give everything needed to guide the implementations of the various functions.

Closes #4.

[yallop]

Added a test against a particular board (4a0d8c5), to complement the quickcheck tests, which generate boards randomly.

[yallop]

Added tests for the is_full_board and insert_into_board functions (ebd916e and aee84b4 respectively).

[dbuenzli]

Any reason why this wasn't merged yet ?

[lpw25]

Not that I'm aware of, so I've gone ahead and merged it.