BookOps/

Possibility as Container

Imagine a box that might be empty. You can't see inside without opening it. When you open it, you find either nothing---or something valuable.

This simple image captures one of programming's most elegant abstractions: types that represent possibility. Not the thing itself, but the potential presence or absence of the thing.

Remember our partial functions from Chapter~\ref{ch:rules-of-the-game}? Rules created "holes"---inputs that had no valid output. We asked: what should happen when we hit a hole?

The elegant answer is to make the function total. Instead of having holes, we fill them with explicit "no result" values. The function always returns something---it just tells us whether that something is a real answer or an acknowledgment of failure.

A total function with Maybe: every input maps to an output. Invalid inputs map to Nothing.

Maybe: Presence or Absence

The Maybe type (also called Option or Optional) represents a value that might not exist:

    Maybe A:
        Nothing OR
        Just(value: A)

Read this as: "A Maybe A is either Nothing, or it's Just some value of type A."

    Maybe Number:
        Nothing OR Just(42) OR Just(0) OR Just(-7) ...
    
    Maybe Piece:
        Nothing OR Just(white king) OR Just(black pawn) ...

Every function that might not find what it's looking for can return Maybe:

python
    find_piece_at(board, square): Maybe Piece
    find_king(board, color): Maybe Square
    parse_number(text): Maybe Number

Result: Success or Failure

Sometimes we don't just want to know if something exists---we want to know why it failed:

    Result A E:
        Success(value: A) OR
        Failure(error: E)

Read this as: "A Result A E is either a Success containing an A, or a Failure containing an E."

    validate_move(state, move): Result ChessState MoveError
    
    MoveError:
        NoPieceAtSource OR
        WrongColorPiece OR
        IllegalMovement OR
        WouldLeaveKingInCheck

Now callers know exactly what might go wrong:

    match validate_move(state, attempted):
        case Success(new_state):
            "Move applied!"
        case Failure(NoPieceAtSource):
            "There's no piece on that square"
        case Failure(WrongColorPiece):
            "That's not your piece"
        case Failure(WouldLeaveKingInCheck):
            "That move would leave your king in check"
        ...

Working with Containers

These container types are powerful, but they create a problem. If we have a Maybe Piece, how do we work with the piece inside?

Suppose we want the color of a piece---but we only have a Maybe Piece:

    maybe_piece: Maybe Piece = find_piece_at(board, e4)
    
    // We want the color, but we have Maybe Piece, not Piece
    // Naive approach:
    match maybe_piece:
        case Nothing:
            Nothing
        case Just(piece):
            Just(piece.color)

This works, but it's tedious. We're repeating the same pattern: "if Nothing, return Nothing; if Just, transform the contents."

Map: Transforming Contents

We can abstract this pattern into a function called map:

    map(container, transform):
        match container:
            case Nothing:
                return Nothing
            case Just(value):
                return Just(transform(value))

Visually, map is a branching flow---two rails, one for each possibility:

The map function as a railway: Nothing passes through unchanged; Just(x) gets transformed.

Now our code becomes:

python
    maybe_piece = find_piece_at(board, e4)
    maybe_color = map(maybe_piece, (p) => p.color)

Read this procedurally: "Take the maybe-piece, and if there's a piece inside, get its color."

We can also read this declaratively, through substitution:

maybe_color is:

  • If maybe_piece is Just(piece), then Just(piece.color)
  • If maybe_piece is Nothing, then Nothing

And since maybe_piece is find_piece_at(board, e4), this reads as:

"maybe_color is the color of the piece at e4, if one exists---otherwise nothing."

Chaining Operations

What if our transformation itself returns a Maybe? Suppose we want to find the king, then find its square, then find what's attacking it:

python
    find_king(board, white): Maybe Square
    find_attacker(board, square): Maybe Piece

If we use map:

python
    maybe_square = find_king(board, white)
    maybe_maybe_attacker = map(maybe_square, (sq) => find_attacker(board, sq))
    // Oops! We get Maybe (Maybe Piece)

We need a way to "flatten" nested containers. This is called flatMap (or bind or chain):

    flatMap(container, transform):
        match container:
            case Nothing:
                return Nothing
            case Just(value):
                return transform(value)   // transform returns Maybe
flatMap: the transform itself returns Maybe, so no extra wrapping needed.

Now:

python
    maybe_square = find_king(board, white)
    maybe_attacker = flatMap(maybe_square, (sq) => find_attacker(board, sq))
    // Clean: Maybe Piece

We can chain multiple operations:

scala
    result = flatMap(find_king(board, white), (king_square) =>
             flatMap(find_attacker(board, king_square), (attacker) =>
             Just(attacker.kind)))

If any step returns Nothing, the whole chain returns Nothing. Failure propagates automatically---no nested if-statements, no forgotten checks.

The Functor Pattern

The map operation isn't specific to Maybe. It works for any container:

python
    // map over List
    map([1, 2, 3], (x) => x * 2)        // [2, 4, 6]
    
    // map over Maybe  
    map(Just(5), (x) => x * 2)          // Just(10)
    map(Nothing, (x) => x * 2)          // Nothing
    
    // map over Result
    map(Success(5), (x) => x * 2)       // Success(10)
    map(Failure(err), (x) => x * 2)     // Failure(err)

Any type that supports map is called a functor. Functors are containers we can "see inside" and transform.

The functor laws ensure map behaves sensibly:

  1. Mapping the identity function changes nothing: map(x, id) == x
  2. Mapping composed functions is the same as composing maps: map(x, f∘g) == map(map(x, g), f)

The Power of Containers

These container types---Maybe, Result, and their operations map/flatMap---give us:

elixir
    // A pipeline of operations, any of which might fail:
    result = 
        parse_move(input)
        |> flatMap((move) => validate_move(state, move))
        |> map((new_state) => new_state.turn)
    
    // result is Result Color MoveError
    // All error cases handled, compiler verified
  1. Explicit types: The signature tells us what might go wrong
  2. Compiler checking: We can't forget to handle failure
  3. Composability: Operations chain cleanly
  4. No effects: Failure is a value, not an interruption

Try It Yourself

Try It Yourself

6 exercises to practice

We've learned to encode possibility in types, making failure explicit and composable. But so far, our systems exist in a single moment. What about systems that remember? That can undo? That travel through time?

In the next part, we explore time, memory, and the persistence of state.