Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

choosing a monad at runtime

I'm trying to write a two-player game in Haskell, such as checkers. I envision having types GameState, Move, and a function result :: GameState -> Move -> GameState that defines the game rules. I want to have both human and automated players, and I figured I'd do this by having a typeclass:

class Player p m | p -> m where
  selectMove :: p -> GameState -> m Move

where the idea would be that m could be Identity for a basic AI player, IO for a human, State for an AI that maintains state across moves, etc. The question is how to go from these to the overall game loop. I figure I could define something like:

Player p1 m1, Player p2 m2 => moveList :: p1 -> p2 -> GameState -> m1 m2 [Move]

a monadic function that takes in the players and initial state, and returns the lazy list of moves. But then on top of this let's say I want a text-based interface that, say, allows first selecting each player from a list of possibilities, then causes the game to be played. So I'd need:

playGame :: IO () 

I can't see how to define playGame given moveList in a generic way. Or is my overall approach not right?

EDIT: thinking further about it, I don't even see how to define moveList above. E.g., if player 1 was a human, so IO, and player 2 was a stateful AI, so State, the first move of player 1 would have type IO Move. Then player 2 would have to take the resulting state of type IO GameState and produce a move of type State IO Move, and player 1's next move would be of type IO State IO Move? That doesn't look right.

like image 871
bhaskarama Avatar asked Oct 13 '12 23:10

bhaskarama


2 Answers

There are two parts to this question:

  • How to mix a monad-independent chess-playing framework with incremental monad-specific input
  • How to specify the monad-specific part at run time

You solve the former problem using a generator, which is a special case of a free monad transformer:

import Control.Monad.Trans.Free -- from the "free" package

type GeneratorT a m r = FreeT ((,) a) m r
-- or: type Generator a = FreeT ((,) a)

yield :: (Monad m) => a -> GeneratorT a m ()
yield a = liftF (a, ())

GeneratorT a is a monad transformer (because FreeT f is a monad transformer, for free, when f is a Functor). This means we can mix yield (which is polymorphic in the base monad), with monad-specific calls by using lift to invoke the base monad.

I'll define some fake chess moves just for this example:

data ChessMove = EnPassant | Check | CheckMate deriving (Read, Show)

Now, I'll define an IO based generator of chess moves:

import Control.Monad
import Control.Monad.Trans.Class

ioPlayer :: GeneratorT ChessMove IO r
ioPlayer = forever $ do
    lift $ putStrLn "Enter a move:"
    move <- lift readLn
    yield move

That was easy! We can unwrap the result one move at a time using runFreeT, which will only demand the player input a move when you bind the the result:

runIOPlayer :: GeneratorT ChessMove IO r -> IO r
runIOPlayer p = do
    x <- runFreeT p -- This is when it requests input from the player
    case x of
        Pure r -> return r
        Free (move, p') -> do
            putStrLn "Player entered:"
            print move
            runIOPlayer p'

Let's test it:

>>> runIOPlayer ioPlayer
Enter a move:
EnPassant
Player entered:
EnPassant
Enter a move:
Check
Player entered:
Check
...

We can do the same thing using the Identity monad as the base monad:

import Data.Functor.Identity

type Free f r = FreeT f Identity r

runFree :: (Functor f) => Free f r -> FreeF f r (Free f r)
runFree = runIdentity . runFreeT

NoteThe transformers-free packages defines these already (Disclaimer: I wrote it and Edward merged its functionality was merged into the free package. I only keep it for teaching purposes and you should use free if possible).

With those in hand, we can define pure chess move generators:

type Generator a r = Free ((,) a) r
-- or type Generator a = Free ((,) a)

purePlayer :: Generator ChessMove ()
purePlayer = do
    yield Check
    yield CheckMate

purePlayerToList :: Generator ChessMove r -> [ChessMove]
purePlayerToList p = case (runFree p) of
    Pure _ -> []
    Free (move, p') -> move:purePlayerToList p'

purePlayerToIO :: Generator ChessMove r -> IO r
purePlayerToIO p = case (runFree p) of
    Pure r -> return r
    Free (move, p') -> do
        putStrLn "Player entered: "
        print move
        purePlayerToIO p'

Let's test it:

>>> purePlayerToList purePlayer
[Check, CheckMate]

Now, to answer your next question, which is how to choose the base monad at run time. This is easy:

main = do
    putStrLn "Pick a monad!"
    whichMonad <- getLine
    case whichMonad of
        "IO"     -> runIOPlayer ioPlayer
        "Pure"   -> purePlayerToIO purePlayer
        "Purer!" -> print $ purePlayerToList purePlayer

Now, here is where things get tricky. You actually want two players, and you want to specify the base monad for both of them independently. To do this, you need a way to retrieve one move from each player as an action in the IO monad and save the rest of the player's move list for later:

step
 :: GeneratorT ChessMove m r
 -> IO (Either r (ChessMove, GeneratorT ChessMove m r))

The Either r part is in case the player runs out of moves (i.e. reaches the end of their monad), in which case the r is the block's return value.

This function is specific to each monad m, so we can type class it:

class Step m where
    step :: GeneratorT ChessMove m r
         -> IO (Either r (ChessMove, GeneratorT ChessMove m r))

Let's define some instances:

instance Step IO where
    step p = do
        x <- runFreeT p
        case x of
            Pure r -> return $ Left r
            Free (move, p') -> return $ Right (move, p')

instance Step Identity where
    step p = case (runFree p) of
        Pure r -> return $ Left r
        Free (move, p') -> return $ Right (move, p')

Now, we can write our game loop to look like:

gameLoop
 :: (Step m1, Step m2)
 => GeneratorT ChessMove m1 a
 -> GeneratorT ChessMove m2 b
 -> IO ()
gameLoop p1 p2 = do
    e1 <- step p1
    e2 <- step p2
    case (e1, e2) of
        (Left r1, _) -> <handle running out of moves>
        (_, Left r2) -> <handle running out of moves>
        (Right (move1, p2'), Right (move2, p2')) -> do
            <do something with move1 and move2>
            gameLoop p1' p2'

And our main function just selects which players to use:

main = do
    p1 <- getStrLn
    p2 <- getStrLn
    case (p1, p2) of
        ("IO", "Pure") -> gameLoop ioPlayer purePlayer
        ("IO", "IO"  ) -> gameLoop ioPlayer ioPlayer
        ...

I hope that helps. That was probably a bit over kill (and you can probably use something simpler than generators), but I wanted to give a general tour of cool Haskell idioms that you can sample from when designing your game. I type-checked all but the last few code blocks, since I couldn't come up with a sensible game logic to test on the fly.

You can learn more about free monads and free monad transformers if those examples didn't suffice.

like image 127
Gabriella Gonzalez Avatar answered Nov 11 '22 17:11

Gabriella Gonzalez


My advice has two main parts:

  1. Skip defining a new type class.
  2. Program to the interfaces defined by existing type classes.

For the first part, what I mean is you should consider creating a data type like

data Player m = Player { selectMove :: m Move }
-- or even
type Player m = m Move

What the second part means is to use classes like MonadIO and MonadState to keep your Player values polymorphic, and choose an appropriate monad instance only at the end after combining all the players. For example, you might have

computerPlayer :: MonadReader GameState m => Player m
randomPlayer :: MonadRandom m => Player m
humanPlayer :: (MonadIO m, MonadReader GameState m) => Player m

Perhaps you will find there are other players you want, too. Anyway, the point of this is that once you've created all these players, if they are typeclass polymorphic as above, you may choose a particular monad that implements all the required classes and you are done. For example, for these three, you might choose ReaderT GameState IO.

Good luck!

like image 25
Daniel Wagner Avatar answered Nov 11 '22 16:11

Daniel Wagner