Composing types

In the previous article about opaque types we touched upon the idea of make illegal states unrepresentable by asking the simple question:

Are all possible String values a valid email address?

The same question can be asked for more complex types. Those that are composed of other types.

For example how are we going to model playing card?

enum Face { Ace, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Jack, Queen, King }
enum Suit { Diamond, Heart, Club, Spade }
record Card(@Nonnull Face face, @Nonnull Suit suit) {}

Product type

Types that encode and relationship we call product types. In the card example we have a type that contains a Face and a Suit.

There is another way to look at the type. We can think of it as a description of a set of values. Then we can measure the size/cardinality of that set. I annotate size/cardinality of Type as |Type|
For example:

Hence the name Product type. If it is not clear why we multiply the size, think of all possible inputs that Card can accept.

But how is that useful?

Well we know that all playing cards are exactly 52 and the cardinality of the Card type is 52 so there is nothing to worry about - all possible inputs create valid playing card.

How about if we want jokers as well? Who doesn't like jokers?

record Card(@Nonnull Face face, @Nonnull Suit suit, boolean isJoker) {}

No brainer, right?

Let's calculate the cardinality of Card though.

Our possible instances are way bigger than the expected 54 cards - 52 playing cards and 2 jokers.

Card illegal = new Card(Face.Two, Suit.Spades, true);

One may argue that this is not illegal card because it is stating which card is being substituted by the joker. However this encoding does not represent our domain correctly. We can reach out to smart constructors to solve this, but we have something more powerful.

Sum types

Types that encode or relationship we call sum types. Your intuition might be I am talking about enums like Face, but those are crippled version of sum type.
Look.

enum Face { Ace, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Jack, Queen, King }
enum Suit { Diamond, Heart, Club, Spade }
enum JokerColor { Red, Black }
sealed interface Card {
    record PlayingCard(@Nonnull Face face, @Nonnull Suit suit) implements Card {}
    record Joker(@Nonnull JokerColor color) implements Card {}
}

We have two types of Card either PlayingCard or Joker. Each variant accepts different type of arguments - better than enums, no?

Since we are calling it sum type it is kind of obvious how are we going to calculate cardinality. Let's compute.

While it might not feel like big accomplishment that we are combining sum and product types, notice that:

• we can not produce invalid Card
• we introduced zero logic
• domain is communicated clearly - meaning vs encoding
• the compiler will ensure that everybody complies with the domain

Let's see how we can extend this list with

State machines

For that we will need slightly more complex problem. We will continue with cards. But this time we need Deck of Cards:

• we can have initial Deck as if it is brand new one
• we can have shuffled Deck that is ... well shuffled
• and last but not least we can have empty Deck

Expected behavior for a Deck is to:

• make InitialDeck of cards
• shuffle it before each game
• deal from the ShuffledDeck until
• we get EmptyDeck

The only addition to our code that seems to be needed is

sealed interface Deck {
    final class InitialDeck implements Deck {
        private final SortedSet<Card> cards;
        private InitialDeck(@Nonnull SortedSet<Card> cards) { this.cards = cards; }
    }
    final class ShuffledDeck implements Deck {
        private final Set<Card> cards;
        private ShuffledDeck(@Nonnull Set<Card> cards) { this.cards = cards; }
    }
    final class EmptyDeck implements Deck {}

    static InitialDeck make() {
        // produce all combinations of Face and Suit - all cards
    }
    static ShuffledDeck shuffle(InitialDeck deck) {
        // pick your favourite shuffling algorithm
    }
    static Deck deal(ShuffledDeck deck, Consumer<Card> consumer) {
        // deal until you can't
    }
}

Good. Now we can think of InitialDeck, ShuffledDeck and EmptyDeck as nodes in state machine while make, shuffle and deal as transition between the nodes.

Now we have enforced all requirements:

• there is only one way to create InitialDeck - through smart constructor make
• you can create ShuffledDeck only if you have InitialDeck beforehand
• you can deal only from ShuffledDeck - dealing from EmptyDeck or InitialDeck would be mistake
• you can empty a Deck only if you deal all it's cards

Summary

We saw how using product and sum types we can represent domain knowledge that will further be enforced and illegal states will not be possible. Also if we employ once again the idea of smart constructors we can produce small state machines correctly describe workflow in the domain.

The idea of type algebra and cardinality is quite powerful and we only scratched the surface with this article. If you are hungry for more you can check out:

• Algebra and Data Types - awesome article that dives deeper and as final result encodes invariants of red-black tree into a type. How cool is that?
• The Algebra of Algebraic Data Types 3 part series that goes as far as differentiating types