State monad

Game engines, pure state management

Published:
state-monad monad functional-programming category-theory state-management pure-functions haskell typescript csharp game-engines behavior-trees parser-combinators 
 ____ _____  _  _____ _____   __  __  ___  _   _    _    ____  ____
/ ___|_   _|/ \|_   _| ____| |  \/  |/ _ \| \ | |  / \  |  _ \/ ___|
\___ \ | | / _ \ | | |  _|   | |\/| | | | |  \| | / _ \ | | | \___ \
 ___) || |/ ___ \| | | |___  | |  | | |_| | |\  |/ ___ \| |_| |___) |
|____/ |_/_/   \_\_| |_____| |_|  |_|\___/|_| \_/_/   \_\____/|____/

So, you've mastered monads. You can chain computations like a pro, handle errors gracefully, and your code flows like poetry. You're feeling pretty good about yourself, maybe even a little smug. Then someone mentions "state management" and suddenly you're back to playing hot potato with mutable variables, passing state objects around like they're contagious, and wondering if there's a better way.

Well, good news! There is. Meet the State monad[1]. It has a Reader-like side, because each step can inspect the current state, and a Writer-like side, because each step produces state for the next one. The important difference is that Writer accumulates output with a monoid, while State threads one evolving state value through a sequence of computations.

The State monad is like having a really good secretary who not only keeps track of everything for you but also knows exactly what you need next. No more "wait, what was I doing again?" moments. No more accidentally overwriting important data. Just smooth, stateful computations that feel natural and composable.

The Problem #

Imagine you're building a video game where you need to track the player's health, score, inventory, and position. Every action—collecting items, taking damage, moving—needs to modify this state while also potentially returning some result.

This approach works, but it's tedious and error-prone. We have to manually thread the state through every operation, remember to use the updated state, and handle the state transformation boilerplate repeatedly.

What if we could abstract away the state threading and focus on the core game logic? This is exactly what the State monad provides.

From Reader and Writer to State #

In our monads article, we explored how Reader applicative and Writer applicative handle different aspects of computation:

  • Reader: Computations that consume a shared environment
  • Writer: Computations that produce accumulated output

The State monad brings both intuitions into one state-threading pattern:

  • Read the current state (like Reader)
  • Produce the next state (Writer-like, but replacing/threading rather than accumulating)
  • Thread state sequentially through computations (monadic chaining)

Categorical Perspective #

From a category theory perspective, the State monad State s a represents computations that:

  1. Input: Take an initial state of type s
  2. Output: Produce a result of type a and a new state of type s
  3. Structure: State s a ≅ s -> (a, s) - a function from state to a pair of result and new state

This captures the essence of stateful computation: functions that transform state while producing results.

State Monad Definition #

The State monad is defined as:

newtype State s a = State { runState :: s -> (a, s) }

Where:

  • s is the type of the state
  • a is the type of the result value
  • runState unwraps the state computation function

Core Operations #

There are three fundamental operations:

  1. get: Read the current state
  2. put: Replace the state
  3. modify: Update the state with a function
-- Get the current state
get :: State s s
get = State $ \s -> (s, s)

-- Replace the state
put :: s -> State s ()
put newState = State $ \_ -> ((), newState)

-- Modify the state with a function
modify :: (s -> s) -> State s ()
modify f = State $ \s -> ((), f s)

Monad Instance #

instance Functor (State s) where
    fmap f (State g) = State $ \s ->
        let (a, s') = g s
        in (f a, s')

instance Applicative (State s) where
    pure a = State $ \s -> (a, s)
    State f <*> State g = State $ \s ->
        let (func, s') = f s
            (a, s'') = g s'
        in (func a, s'')

instance Monad (State s) where
    return = pure
    State g >>= f = State $ \s ->
        let (a, s') = g s
            State h = f a
        in h s'

The key insight is in the bind operation: it runs the first computation, extracts both the result and the new state, passes the result to the next computation, and threads the state through the sequence.

Examples #

Let's implement the State monad[3] in different languages and see how it simplifies our game example.

Visualizing State Monad #

1. State threads through each computation

State s a = s -> (a, s)

      input state        state computation          result + next state
    +-------------+     +-------------------+     +-------------------+
    |     S0      | --> | run step1 with S0 | --> |    (A1, S1)       |
    +-------------+     +-------------------+     +---------+---------+
                                                            |
                                                            | thread S1
                                                            v
                          +-------------------+     +-------------------+
                          | run step2 with S1 | --> |    (A2, S2)       |
                          +-------------------+     +---------+---------+
                                                            |
                                                            | thread S2
                                                            v
                          +-------------------+     +-------------------+
                          | run step3 with S2 | --> |    (A3, S3)       |
                          +-------------------+     +-------------------+

The result value A is exposed to the next bind.
The state value S is quietly passed forward.


2. Game example flow

    +----------------------------------------------------------------+
    | health: 100 | score:  0 | inventory: []        | pos: (0, 0)   |
    +----------------------------------------------------------------+
             |
             | collectItem("sword")
             | result: "Collected sword"
             v
    +----------------------------------------------------------------+
    | health: 100 | score: 10 | inventory: ["sword"] | pos: (0, 0)   |
    +----------------------------------------------------------------+
             |
             | takeDamage(20)
             | result: "Still alive"
             v
    +----------------------------------------------------------------+
    | health:  80 | score: 10 | inventory: ["sword"] | pos: (0, 0)   |
    +----------------------------------------------------------------+
             |
             | movePlayer(5, 3)
             | result: "Moved to (5, 3)"
             v
    +----------------------------------------------------------------+
    | health:  80 | score: 10 | inventory: ["sword"] | pos: (5, 3)   |
    +----------------------------------------------------------------+


3. Manual threading vs bind

Manual threading:

    state0
      |
      v
    step1(state0) -> (result1, state1)
                                 |
                                 v
    step2(state1) -> (result2, state2)
                                 |
                                 v
    step3(state2) -> (result3, state3)

Every call must use the state returned by the previous call.

State monad:

    step1 >>= step2 >>= step3

    bind runs each step,
    passes its result to the next function,
    and threads the new state into the next computation.

Common State Monad Patterns #

Accumulator Pattern #

The accumulator pattern uses the State monad to maintain running totals, counts, or other accumulated values while processing data. In Haskell, these examples use Control.Monad.State[2].

Generator Pattern #

The generator pattern uses the State monad to generate sequences of unique values, such as IDs or random numbers.

Parser State Pattern #

The parser pattern uses the State monad to track position and remaining input while parsing structured data.[a]

Configuration Management Pattern #

The configuration pattern uses the State monad to manage application settings and feature toggles dynamically.

Stateful Validation Pattern #

The validation pattern uses the State monad to accumulate validation errors while building up a context of validated data.

Behavior Trees #

Behavior trees are a popular AI pattern used in game development[4] to create complex, hierarchical decision-making systems for NPCs (Non-Player Characters). The State monad is perfect for implementing behavior trees because each behavior needs to:

  1. Read the current AI state (position, health, targets, etc.)
  2. Modify the state based on decisions (move, attack, change targets)
  3. Return success/failure status to parent behaviors
  4. Chain behaviors together in a decision hierarchy

Let's build a simple AI behavior tree using the State monad:

How Behavior Tree Works #

The behavior tree follows this decision hierarchy:

AI Turn
├── Find Target (Always succeeds)
└── Has Target?
    ├── YES → Try Attack
    │   ├── Attack Success? → "Attacked!"
    │   └── Attack Failed → Try Move
    │       ├── Move Success? → "Moved toward target"
    │       └── Move Failed → "Standing still"
    └── NO → "Looking for target"

Behavior Trees - Why State Monad #

  1. Automatic State Threading: Each behavior automatically receives the current AI state and passes the updated state to the next behavior.

  2. Composability: Complex behaviors can be built by combining simpler behaviors using monadic operations.

  3. Decision Chaining: The do notation makes it easy to express "try this, if it fails try that" logic.

  4. Pure Functions: All behaviors remain pure functions, making them easy to test and reason about.

This example shows how the State monad enables complex AI behaviors while keeping the code clean and composable. Each behavior can focus on its specific logic while the State monad handles all the state management automatically.

State Monad vs Other Approaches #

Comparison Table #

Approach State Threading Error Handling Composability Readability
Manual Manual/Error-prone Manual Poor Poor
State Monad Automatic Needs another layer Excellent Excellent
Object-Oriented Implicit/Mutable Exceptions Moderate Moderate
Functional (Pure) Explicit passing Result types Good Good

State Monad Usage #

Use State Monad when:

  • You have sequential operations that modify shared state
  • State transformations are the primary concern
  • You want pure functional state management
  • You need composable stateful computations

Consider alternatives when:

  • State is simple and rarely changes
  • You need shared mutable state across threads
  • Performance is critical and State monad overhead matters
  • Your team is not familiar with monadic patterns

Conclusion #

The State monad solves the problem of threading state through sequential computations. By abstracting away the manual state passing, it allows us to focus on the core logic while maintaining the benefits of pure functions.

Key benefits of the State monad:

  1. Automatic State Threading: No more manual state passing and potential errors
  2. Composability: State operations compose naturally using monadic combinators
  3. Purity: Stateful computations remain pure functions
  4. Abstraction: Clean separation between state management and business logic
  5. Flexibility: Easy to combine with other monads (IO, Error handling, etc.)

Source code #

Reference implementation

Notes

  1. These examples are simple cursor parsers: a failed parse returns `Nothing`, but State alone does not provide automatic backtracking. If you need rollback-on-failure, use a parser abstraction that restores state on failure, or choose the transformer ordering deliberately. For example, `MaybeT (State s)` preserves state changes before failure, while `StateT s Maybe` discards the final state when the computation fails. ·

References

  1. State monad ·
  2. Control.Monad.State - Haskell ·
  3. State Monad Tutorial ·
  4. Game Programming with State Monads ·

Continue exploring