Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 3 / a

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, 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.