= Solution
Use coordinates with row and column in $\{0,1,2\}$:
``
type Place = (Int,Int)
type Places = [Place]
type Board = (Places,Places,Places)
data Player = O | X deriving (Eq,Ord,Show)
``
The components of `Board` record the positions occupied by `O`, occupied by `X`, and still empty, respectively. On a nonterminal legal board, \b[equal occupied counts mean `O` moves next; one extra `O` means `X` moves next].
The <type synonym> does not enforce the <representation invariant>: coordinates are in range; each component has no duplicates; the three represented <sets> form a <set partition> of the nine positions; and the occupied counts differ as just described. Both players cannot have won. A winning `O` board has one extra `O`, and a winning `X` board has equal counts. More fundamentally, a legal <tic-tac-toe> state has a legal alternating history that stops at the first win: satisfying a type alone never licenses continuing an already completed game.
Back to article page
