Type safety with ts

tic-tac-toc.ts

/*
  Type Tac Toe: Advanced Type Safety
  ==================================
  Adapted from http://chrispenner.ca/posts/type-tac-toe
*/

/** Either X, O, or Nothing */
type Piece = 'X' | 'O' | 'N'

/** coordinates */
type Coord = 'A' | 'B' | 'C'

interface Empty {
  isEmpty: 'T'
  X: never
  Y: never
  T: never
  Rep: never
}

type TurnX = 'X'
type TurnO = 'O'
type Turn = TurnX | TurnO

interface Cons<X extends Coord, Y extends Coord, T extends Turn, Rep extends BoardRep> {
  isEmpty: 'F'
  X: X
  Y: Y
  T: T
  Rep: Rep
}

/** Keep a list of each Piece played and its location */
type BoardRep = Empty | Cons<any, any, any, any>

class Triple<A> {
  constructor(readonly a: A, readonly b: A, readonly c: A) {}
}

/** A board is a 3x3 grid alongside its type representation */
class Board<Rep extends BoardRep, A> {
  _Rep: Rep
  constructor(readonly value: Triple<Triple<A>>) {}
}

const newTrip = new Triple<Piece>('N', 'N', 'N')

/** New empty board */
const newBoard = new Board<Empty, Piece>(new Triple(newTrip, newTrip, newTrip))

/** Utility function to alter a value inside a triple */
const overTrip = (coord: Coord) => <A>(f: (a: A) => A) => (trip: Triple<A>): Triple<A> => {
  switch (coord) {
    case 'A':
      return new Triple(f(trip.a), trip.b, trip.c)
    case 'B':
      return new Triple(trip.a, f(trip.b), trip.c)
    case 'C':
      return new Triple(trip.a, trip.b, f(trip.c))
  }
}

/** type-level booleans */
type Bool = 'T' | 'F'

type If<B extends Bool, Then, Else> = {
  T: Then
  F: Else
}[B]

type Not<B extends Bool> = If<B, 'F', 'T'>

type And<B1 extends Bool, B2 extends Bool> = If<B1, B2, 'F'>

/** return 'T' if A and B are equal */
type Eq<A extends string, B extends string> = ({ [K in A]: 'T' } & {
  [key: string]: 'F'
})[B]

/** return 'T' if a square has been played already **/
type IsPlayed<X extends Coord, Y extends Coord, B extends BoardRep> = {
  T: 'F'
  F: If<And<Eq<B['X'], X>, Eq<B['Y'], Y>>, 'T', IsPlayed<X, Y, B['Rep']>>
}[B['isEmpty']]

/**
 * Play a piece on square (x, y) if it's valid to do so.
 * Alas I need an additional argument here to prove that IsPlayed<X, Y, Rep> is 'F'
 */
const playX = <X extends Coord, Y extends Coord>(x: X, y: Y) => <
  Rep extends Empty | Cons<any, any, TurnO, any>,
  Proof extends Not<IsPlayed<X, Y, Rep>>
>(
  board: Board<Rep, Piece>,
  proof: Proof & 'T'
): Board<Cons<X, Y, TurnX, Rep>, Piece> => new Board(overTrip(y)(overTrip(x)((): Piece => 'X'))(board.value))

const playO = <X extends Coord, Y extends Coord>(x: X, y: Y) => <
  Rep extends Empty | Cons<any, any, TurnX, any>,
  Proof extends Not<IsPlayed<X, Y, Rep>>
>(
  board: Board<Rep, Piece>,
  proof: Proof & 'T'
): Board<Cons<X, Y, TurnO, Rep>, Piece> => new Board(overTrip(y)(overTrip(x)((): Piece => 'O'))(board.value))

//
// usage
//

const show = (board: Board<any, Piece>): string => `
${board.value.a.a} | ${board.value.a.b} | ${board.value.a.c}
${board.value.b.a} | ${board.value.b.b} | ${board.value.b.c}
${board.value.c.a} | ${board.value.c.b} | ${board.value.c.c}
`

const proof: 'T' = 'T'

console.log(show(newBoard))

// board1: Board<Cons<"A", "B", "X", Empty>, Piece>
const board1 = playX('A', 'B')(newBoard, proof) // ok
console.log(show(board1))

playX('A', 'A')(board1, proof) // nope... it's O's turn!
playO('A', 'B')(board1, proof) // nope... already played!

// board2: Board<Cons<"A", "A", "O", Cons<"A", "B", "X", Empty>>, Piece>
const board2 = playO('A', 'A')(board1, proof) // ok
console.log(show(board2))