Skip to the content ForoHackers
Log inJoin

Make illegal states unrepresentable (algebraic data types in ten minutes)

Functional programmingHaskellType theory
#1170 · lambda_llama · · Report

A pattern that changes how you design data, and the reason I keep telling people to look at sum types.

Typical connection object in a language without them:

class Connection:
    connected: bool
    socket: Socket | None
    retry_count: int | None
    error: str | None

How many of the combinations make sense? connected=True with socket=None? connected=False with an error and a retry_count? Every function that touches this has to remember which fields are valid when. Some do not. That is where the bugs live.

Same thing as a sum type:

data Connection
  = Disconnected
  | Connecting Int          -- attempt number
  | Connected Socket
  | Failed String

Four states, and each one carries only the data that exists in that state. There is no way to build a Connected without a socket, because the socket is part of the constructor.

Using it:

describe :: Connection -> String
describe Disconnected    = "idle"
describe (Connecting n)  = "attempt " ++ show n
describe (Connected _)   = "online"
describe (Failed msg)    = "failed: " ++ msg

If you later add a fifth state and forget to handle it, the compiler can warn you about the non-exhaustive match. The bug is caught before the program runs.

The same idea exists as enum with data in Rust, as tagged unions in several other languages, and as discriminated unions in typed JavaScript dialects. You do not need Haskell to use it. You only need the habit of asking: "which combinations of these fields are impossible, and can I make the type refuse them?"

#1989 · monad_tutorial_no_47 · · Report

I appreciate that this tutorial contains no burrito and no category theory. Growth.

#1990 · tabs_over_spaces_42 · · Report

This is the most convincing argument for sum types I have seen, and I say that as someone who has written the four-booleans class and shipped it. The giveaway in review: any comment that says "only valid if connected is true".

#1991 · TortillaConSegfault · · Report

En C++ lo más parecido es std::variant con std::visit, y funciona, aunque la sintaxis pide paciencia. Aun así, solo por no tener un socket nulo cuando "está conectado", merece la pena.

#1992 · race_condition_rita · · Report

A sum type fixes "which fields are valid in which state", and it does not fix "which transitions are legal". Nothing in this type stops Failed going straight to Connected. For that you go further: encode the state in the type of the handle, so that the function connect only accepts a Disconnected. It is the same instinct, one step further.

Log in or join to reply.