Representing game state with typeclass in Haskell

Question

I'm implementing some functions to search game trees for my own amusement. For example, one such function would execute the Minimax algorithm. These functions are using two kinds of objects:

1. Game state, e.g. the positions of the pieces on a chess board, the next player to move, etc.
2. Moves, e.g. "Pawn e2 to e5"

My goal is to have search functions that work for different games, so I'm passing in game-specific knowledge as helper functions like:

• Generate all possible moves from a given game state
• Given a state and a move, apply the move to the state to get the resulting state
• Find out if this is a winning position
• etc.

This way, my search function is indeed not game-specific, but the solution still doesn't feel right. It also makes my parameter lists rather long:

-- Given a game state find the best next move
bestMove :: s -> (s -> [m]) -> (s -> m -> s) -> m    -- more parameters in my real code
bestMove currentState possibleMoves applyMove = ...

Question

Can I replace these helper functions with typeclasses? I'm looking for something along the lines of this:

class Move m where
  apply :: State s => s -> m -> s

class State s where
  possibleMoves :: Move m => s -> [m]

bestMove :: State s => Move m => s -> m
bestMove currentState = ... -- e.g. = head $ possibleMoves state

The problem is that any instance of State is only supposed to work together with one specific instance of Move and vice versa:

{-# LANGUAGE InstanceSigs #-} 

data ChessState = ...
data ChessMove  = ...

instance Move ChessMove where
  apply :: ChessState -> ChessMove -> ChessState
  apply s m = ...

The type signature for apply is of course wrong. It should be

apply :: S s => s -> ChessMove -> s

but I do need properties that are specific to ChessState in order to create a ChessMove.

Am I completely on the wrong track with the whole idea or is there a way to encode the relationship between ChessState and ChessMove? I have made some little progress with MultiParamTypeClasses, but it's still not looking the way I was hoping.

Answer 1

First of all, if you can do something without type classes then it's often a good idea to just stay away from them. You can always just make a simpler wrapper for a particular application, especially if you flip the arguments suitably:

bestMove :: (s -> [m]) -> (m -> s -> s) -> s -> m

bestChessMove :: ChessState -> ChessMove
bestChessMove = bestMove possibleChessMoves applyChessMove

That said, I don't find the class you envision unsensible (unlike many an OO class that somebody wants to squeeze into Haskell...). And you're quite on the right track that it should be a multiparam class:

{-# LANGUAGE MultiParamTypeClasses #-} 

class MoveState m s where
  apply :: m -> s -> s
  possibleMoves :: s -> [m]

instance MoveState ChessMove ChessState where
  apply = ...
  possibleMoves = ...

Then

bestMove :: MoveState m s => (s -> Cost) -> s -> m

Actually that class is more general than makes sense though: for any given state type, you probably have only one move type. One way to express this is would be a functional dependency | s -> m; what I usually prefer is to instead make the Move type simple a “property” of the state class:

{-# LANGUAGE TypeFamilies #-} 

class GameState s where
  type Move s :: *
  apply :: Move s -> s -> s
  possibleMoves :: s -> [Move s]

Answer 2

You could consider just passing in the whole darn game tree:

data GameTree m s = GameTree s [(m, GameTree m s)]

bestMove :: GameTree m s -> (s -> Int) -> Maybe m
bestMove gameTree evaluateState = ...

Rely on laziness to expand only the parts of the game tree you actually look at.