Hangman in FP Scala
In programming, it’s quite common to express simple subsets of the system as predefined states and inputs that let your state transition from one state to another. It’s also quite pleasing to see your program as a diagram that then you can discuss with your co-workers. In this post, we will try to model a simple game of Hangman in a somewhat simple model using Finite State Machine(FSM) and Algebraic Data Types(ADTs) as building blocks. Our game might look something like this.
Where the dark dots symbolise start(on the left) and end node(on the right), squares express game states and lines symbolise inputs.
Primitives
To start working on the problem, we first need to define some general rules and write ADTs.
Let’s start by defining some game primitives:
Based on Oxford dictionary a word is “A single distinct meaningful element of speech or writing, used with others (or sometimes alone) to form a sentence and typically shown with space on either side when written or printed.”. Based on the definition, it can’t be empty, so let’s expresses it in that way.
When playing the game, we might try to guess the letter or the word, so let’s express the concept of guessing in the game. In our case, we want to track all the letters and words used, so we can help the player to conquer.
There is no better way of making the game challenging than introducing some life counter.
Also, we want to have a medium to show how awesome we are at the game, so let’s introduce difficulty levels.
Building block
When playing the game, we need to have a mechanism to get new words, display the game, parse the game inputs and talk to the console. So le’ ts express it in Tagless approach.
To model FSM, we need GameStates and Inputs.
Game States can be expressed as a sealed trait of all the states.
Game Inputs can be expressed as a sealed trait of all inputs specifying that game-related inputs are another subset.
Dealing with cumbersome mechanics
So the structural parts are out of the way, but some components like Guesses are tough to work. Let’s change that:
Game Logic
Finally, we can start working on game logic. We need a simple way to combine State and Input. If you squint and look at the FSM model, it looks like (GameState, Input) => F[GameState] , where F is a context that holds information about WordService/Console. If we think of our program as an onion, the first part deals with F can be separated. Let’s call itouterGame . The rest of the game in that case is innerGame . So the outerGame can be expressed as:
and the innerGame can be expressed as:
Now we need to combine layers of our game:
and represent our game loop:
The rest of the code that deals with the implementation of Type Classes can be found in the Github repository.
Conclusion
As you can see, Finite State Machines and Algebraic Data Types are a match made in heaven. The graphical model can be easily transferred to the code just by transforming States and Inputs to their own ADTs and adding the missing dynamic rules.
References
- Game description: https://en.wikipedia.org/wiki/Hangman_(game)
- FSM definition: https://www.youtube.com/watch?v=Qa6csfkK7_I and https://en.wikipedia.org/wiki/Finite-state_machine
- Diagram was made using: draw.io
- Github repository: https://github.com/Algiras/Game-Sandbox/tree/master/src/main/scala/sandbox/Hangman
