## Representing game state with typeclass in Haskell

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:

- Game state, e.g. the positions of the pieces on a chess board, the next player to move, etc.
- 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.

Show source

## Answers ( 2 )

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:

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:

Then

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:You could consider just passing in the whole darn game tree:

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