∘ Category Theory for programmers
🎁 Chapter 3 · Both at once, or one or the other

Two ways
to combine types

A type that carries both an A and a B. A type that holds either an A or a B. Two moves, every ADT you've ever written, and the small surprise that types do arithmetic.

In Chapter 2 we pinned down what objects and arrows really are: types and pure functions. Now we ask a small but enormous question — given two types, what are the natural ways to make a third type out of them?

It turns out there are exactly two, and you've already used both:

  • Both at once. A package that holds an A and a B. A pair. A row in a table. A case class.
  • One or the other. A package that holds an A or a B, and remembers which. Either. A sealed trait. The two outcomes of a flip.

Stick around for the punchline: these two moves correspond to multiplication and addition on the sizes of types. ADTs aren't shaped like algebra — they are algebra.

1Both at once

A "both at once" type carries an A and a B at the same time. In Scala that's a tuple (A, B), or a case class Pair[A, B](a: A, b: B). In Haskell it's (A, B), or data Pair a b = Pair a b. Different syntax, same idea: glue two values into one package.

Once you've made a pair, there are two ways back out of the package — one for each component. They have boringly perfect names:

  • fst : (A, B) → A  — give me the first thing
  • snd : (A, B) → B  — give me the second thing

That's the whole story. A package, and two arrows out. The category-theorist's name for "both at once" is a product, and those two arrows out are called projections. You knew them as _1 and _2.

Interactive · build a tuple |Color| · |Bool| = 3 · 2 = 6 tuples in total
All 6 possible tuples — current one highlighted:
fst → Red · snd → true
💡
Scala's case class is a product. The field names are just nicer projections than _1, _2. Haskell's record syntax is the exact same trick. Anywhere you've ever bundled "two things and you want both," you've built a product.

2One or the other

A "one or the other" type holds an A or a B — and crucially, remembers which one it is. In Scala that's Either[A, B], with two constructors Left(a) and Right(b); or a sealed trait with a couple of cases. In Haskell it's Either a b with constructors Left a and Right b, or any data declaration with a |.

This time the interesting arrows go the other way. Instead of two ways out, you get two ways in:

  • Left : A → Either[A, B]  — wrap an A on the left side
  • Right : B → Either[A, B]  — wrap a B on the right side

Two ways into the package — and from the tag Left/Right you always know which door you came through. The category-theorist's name for "one or the other" is a coproduct (or "sum type"). Same idea flipped upside down: instead of arrows out, arrows in.

Interactive · pick an Either |Bool| + |Color| = 2 + 3 = 5 possible values
Click a constructor — you're picking one of the five inhabitants of Either[Bool, Color]:
tag tells you which side · payload is the value
💡
A Scala sealed trait Shape with three case classes is a coproduct of three things. Pattern matching is just "look at the tag, then look at the payload." The compiler can warn on missing cases because it knows all the doors in.

3Wait — this is just algebra?

Yes. Here's the headline. Count the values a type has — call that its cardinality, written |A|. Then:

|A × B|  =  |A| · |B|
|A + B|  =  |A| + |B|

"Both at once" multiplies the count. "One or the other" adds them. That's where the names product and sum come from — they really do behave like × and +.

A worked example: Bool has 2 values, true and false. So a pair (Bool, Bool) has 2 · 2 = 4 values — and yes, you can count them: (t,t), (t,f), (f,t), (f,f).

Now the surprises start landing:

  • Bool = Unit + Unit. Two cases, no data in either. (Unit is "the type with exactly one value" from Ch.2.)
  • Maybe A = Unit + A. Either nothing (the Unit case is "Nothing") or an A (the "Just" case).
  • Void + A = A. The empty type contributes zero — adding it leaves you alone. (Yes, types have a zero.)
  • Unit × A = A. Pairing with Unit adds no information — Unit is the one. (Yes, types have a one.)

The arithmetic even distributes: A × (B + C) and A × B + A × C have the same cardinality and the same structure (an A paired with "either a B or a C" is the same as "either an (A, B) or an (A, C)"). And there's an exponential lurking — the type A → B has |B||A| values, which is why we'll write it as BA later. File that one away.

Interactive · cardinality calculator Slide |A| and |B|, watch × and + react
3
2
Product · both at once
|A × B| = 3 · 2 = 6
Sum · one or the other
|A + B| = 3 + 2 = 5
Puzzle · which one equals Maybe A? Click once · pick the right shape
A Maybe A is "nothing, or an A." Which type below has exactly the same shape?

4Every ADT is some × and some +

Here's a classic. Define a shape as a circle, a rectangle, or a triangle, each with its own measurements:

data Shape = Circle Float | Rect Float Float | Tri Float Float Float

Read that algebraically. There are three cases joined by | — that's a sum of three things. Inside each case the fields sit side-by-side — that's a product. So the whole type is:

Shape  =  Float  +  (Float × Float)  +  (Float × Float × Float)

Sum types choose. Product types bundle. That's it. Every algebraic data type you've ever written — the "A" in ADT really does mean algebraic — is some recipe of × and +.

Pattern matching is the dual move: first you split on which case of the sum you got (the tag), then you take apart the product fields inside it. Sum out, product out. The compiler can check the cases are exhaustive precisely because it knows the algebraic shape.

5The same idea, in code

Tuples, sealed traits, Either, data ... | .... Side-by-side so you can see the moving parts. Notice how building and taking apart are mirror images: constructors go in, projections and pattern matches come out.


        

      

    


    
    

      
6Check yourself

      

        

          3 questions · instant feedback
          0 / 3
        

        

      

    


    
    

      
7What's next

      

        
You now have all the basic pieces of a category — types, functions that compose, and two universal ways to combine types into bigger ones. Next we look at containers: types like List, Option, Future that wrap a value and let you reach inside without breaking the wrapper.

        
That "reach inside" move is map. The fancy name is functor. We'll derive it from first principles — and see why map(f).map(g) == map(g ∘ f) is the only sensible thing it could possibly do.

      


      
        📦
        

          
Up next · Chapter 4

          
Functors

          
A container that lets functions reach inside without breaking the container. map, but explained from first principles — and the two laws it has to obey.

        

        →