I've been working on implementing games in Haskell. Specifically, rules-driven board/card games.
When these games run, they often need to ask a player to make a move. This involves interacting with the outside world in some way. The most obvious way to do this is to embed your computation in the IO Monad:
type Game a = IO a
-- or
type Game a = StateT GameState IO a
However, now you have the problem that arbitrary IO is expressible as part of a game action, which makes it harder to implement things like state tracking, replay, undo, and especially testing.
While thinking about this problem this morning, I came up with the following way to use existential types to split the game from its actions:
-- p is the type of prompts
-- r is the result type
data Prompt p r = forall a. Prompt (p a) (a -> r)
newtype Game a = Game (Either a (Prompt GamePrompt (Game a)))
So, Game t either immediately gives you a t to use, or gives you a prompt you need to reply to in order to continue the computation. Intuitively, I think this is related to the Continuation monad, but I'm not sure.
Now, a simple use of Prompt would be something like the following:
Prompt [1,3,5] (+1) :: Prompt [] Int
Code that sees this can't extract the values from the list, because they don't know the internal type of the list, but you could use it to implement something that randomly chooses:
chooseRandomly :: RandomGen -> Prompt [] a -> (RandomGen, a)
chooseRandomly gen (Prompt xs f) = (gen', f x)
where (gen', x) = choose gen xs
which uses the helper function choose :: RandomGen -> [a] -> (RandomGen, a)
This by itself is interesting and potentially useful, but where it really starts to shine is when the prompt type is a GADT:
-- a GamePrompt gives you the current game state,
-- which player needs to make a choice,
-- and a choice that player needs to make.
type GamePrompt a = (GameState, Player, GameChoice a)
data GameChoice a where
Act :: GameChoice GamePiece -- what piece should act next
Attack :: GamePiece -> GameChoice AttackType -- how should you attack?
-- etc.
You can now define a prompting function:
prompt :: GameState -> Player -> GameChoice a -> Game a
prompt state who choice = Game $ Right $ Prompt (state,who,choice) $ \a -> Game $ Left a
and use it in the middle of game code:
turn :: GameState -> Player -> Game GameState
turn state who = do
-- ...
piece <- prompt state who Act
attackType <- prompt state who (Attack piece)
-- ...
return newState
Similarily, you can write a prompt handler which gets information from the user:
promptHandler :: GamePrompt a -> IO a
promptHandler (state, who, Act) = pickPiece state who
promptHandler (state, who, AttackType piece) = attackMenu state who piece
-- etc.
The neat thing about this is that on the right side of promptHandler, you know what type you need to return, since it's forced by the type of the GADT. What this means is that pickPiece can have the specialized type GameState -> Player -> IO GamePiece; it's no longer returning a generalized IO a (which is very difficult), but a specific type of object.
Now, in order to finish computing the GameState using promptHandler, you need to be in the IO monad, but there's nothing about the game that requires this! You could just as easily have a pure AI player promptHandlerAI :: GamePrompt a -> a
To tie it all together, you need a viewer function that gets the final result:
runGame :: (forall b. GamePrompt b -> IO b) -> Game a -> IO a
runGame _ (Game (Left result)) = return result
runGame f (Game (Right (Prompt prompt next))) = do
action <- f prompt
runGame f (next action)
runGameAI :: (forall b. GamePrompt b -> b) -> Game a -> a
runGameAI _ (Game (Left result)) = result
runGameAI f (Game (Right (Prompt prompt next))) = runGameAI f (next (f prompt))
Finally, to use any of this we need a Monad implementation for Game:
instance Monad Game where
return a = Game (Left a)
Game (Left a) >>= f = f a
Game (Right (Prompt p fp)) >>= f = Game (Right (Prompt p next))
where next x = fp x >>= f
|
![[info]](http://p-stat.livejournal.com/img/userinfo.gif){kind=small}
ryani's journal
calm
cranky
jubilant
amused
giddy