Recently, as an aside to the proposal for static type annotations in Python, Guido offhandedly noted another suggested improvement to Python, adding ADTs (Algebraic Data Types). This has also come up in discussions about pattern matching, and about existing run-time and compile-time static-typing libraries.

What is an ADT?

Instead of trying to fully define an ADT in formal terms (see Wikipedia, or, better, work through a Haskell tutorial, for that), I'll try to define it in terms of values as you might use them in Python.

Basically, an ADT is either a simple type, a product of ADTs, or a sum of ADTs. That's what makes it "algebraic".

Product types

What is a product of types? It's a tuple: (42, "spam") is of type int * str, or, written more simply, (int, str).*

Often you want to add names to the values, like (answer: 42, manna: "spam"), which is of type (answer: int) * (manna: str), or (answer: int, manna: str). Note the equivalency to the "implicit namedtuple literals" that people suggest for Python every few months.

And often you want to add a name to the tuple itself, making this a full "record" type, like ImportantStuff(answer: 42, manna: "spam"), which is of type ImportantStuff:((answer: int) * (manna: str)) or ImportantStuff(answer: int, manna: str). This is exactly like the namedtuple that Python has today. It's also like a C struct (or Python ctypes.Structure).

Note that none of these is like an OO class, especially Python's rendition of that concept. Besides the fact that classes have methods, they have an arbitrary bag of attributes, not an ordered sequence of them. They may have private attributes that are part of the structure but not part of the interface, and computed attributes that are part of the interface but not part of the structure. And so on. (The classes in weaker OO languages like C++ and Java are closer to record types—which is why C++ just defines "class" and "struct" to mean the same thing, except for the default visibility of their members.)

* Notice that, since a tuple type is just a product of types, a single-element tuple is the exact same thing as its one value. And an empty tuple is a singleton value of some unit type that's the result of not multiplying anything (equivalent to 0 when multiplying integers). Python of course distinguishes single-element tuples from their values: (spam,) != (spam). And Python's closest thing to a unit type is NoneType, whose value, None, is often used inside tuples. So, Python's tuple isn't quite a purist version of an untagged product type. But I think we can ignore that difference here.

Sum types

A sum type is a union of two types. This is the part Python doesn't really have today.

Consider a URL-fetching function, which can return either a successful download, an error download, or a failure to even get an error. (Ignore for now the fact that Python would use an exception for the third case.) So, it might return something like:

    ((headers: Sequence[str], body: Iterable[str])
     | (code: int, description: str, headers: Sequence[str], body: Iterable[str])
     | (errno: int,))

On its own, this isn't very usable; to know which of the three you've gotten, you need to either LBYL the members of the returned record with getattr, or EAFP it by using a try:/except AttributeError:. And consider that, at least with HTTP, successful downloads actually have a code and description, just like failed downloads, meaning the two record types are identical, giving you no way to distinguish them! So often, you will want to tag the values:

    (success: (headers: Sequence[str], body: Iterable[str])
     | failure: (code: int, description: str, headers: Sequence[str], body: Iterable[str])
     | error: (errno: int,))

In practice

Optional/Maybe

Fitting ADTs into Python

Product types

As noted above, Python already has tuples and named record types, but not anonymous record types. How do we add those?

namedtuple

The existing namedtuple works fine for named record types.

The proposals for implicit namedtuple literals have, as far as I know, been coherent (at least Christian Tismer's worked out all of the tricky details and showed that they weren't so tricky after all); the only reason they haven't gone anywhere is that no one could explain a real need for them. So let's just add that, and use it for our anonymous tagged records:

    (answer: 42, manna: "spam")

The type of that is:

    (answer: int, manna: str)

Alternative: typed __slots__

Sum types

Python doesn't have sum types at all, except implicitly. And explicit sum types, especially either tagged sums of anonymous products or sums of named products, are exactly what people are missing when they ask for ADTs in Python.

So, how could we add them?

MyPy Union

MyPy adds a Union type: Union[int, NoneType] (or, more compactly, int | str) is a value that can be either an int or a str.

While this only gives us untagged unions, as noted above, tagged unions are equivalent to untagged unions of record types. So, if we wanted to define a Haskell-like Maybe, we could do this:

    Just = namedtuple('Just', (('value', T,)))
    Nothing = namedtuple('Nothing', ())
    Maybe = Just | Nothing

Also, without pattern matching, the only way to actually use this is with isinstance checks (or EAFP try/except):

    def spam(eggs: Maybe[int]):
        if isinstance(n, Just[int]):
            print('Spam with {} eggs'.format(eggs.value))
        else:
            print('The spam stands alone')

There's nothing theoretically wrong here, but it certainly is ugly.

Swift-style Enum

Consider that a sum type of tagged parameterless type constructors is equivalent to a Python-style Enum, with the constructors mapping to enumeration members:

    Color = (Red | Blue | Green)

    Color = Enum('Color', 'Red Blue Green')

You can do the same things with each (although with slightly different syntax). The question of whether Red, Blue, and Green leak into the parent scope or are attributes of Color arises in exactly the same way for the two cases, and has the same pro and con arguments.

So, what if Enum were extended to allow values to be attached to each member? This is exactly what Swift enumerations are, and this is how Swift handles sum types.

I'm going to assume some extension to the language that allows statically typing variables and attributes, rather than doing it in comments a la MyPy, and I'm going to assume that tuples of types are specified as tuples of types rather than some other syntax, but feel free to translate.

    class Barcode(Enum):
        UPCA: (int, int, int, int) = 1
        QRCode: str = 2

So now, you can do this:

    >>> barcode = Barcode.UPCA(8, 85909, 51226, 3)
    >>> barcode
    <Barcode.UPCA(8, 85909, 51226, 3): 1>
    >>> barcode.value
    (8, 85909, 51226, 3)

Or, if you wanted to name the parts of the UPC-A:

    class Barcode(Enum):
        UPCA: (LL: int, L: int, R: int, RR: int) = 1
        QRCode: str = 2

But still, it looks a lot prettier than using Union.

What about recursion?

So ADTs are just a subset of classes?

Does Python really need this?

The big question is: under what circumstances would you want to use an ADT (whether implemented as an Enum with anonymous nanedtuple values, or otherwise) instead of a class?

If the language had pattern matching that only worked on ADTs, the answer might well be "quite often".

But without pattern matching, or with pattern matching that worked on classes that chose to opt in (as described in my previous blog post), I think it wouldn't be that often.

A paradigm case: JSON

JSON is (quite accidentally) an ADT. You can define it as:

    class JSON(Enum):
        null: NoneType = 0
        boolean: bool = 1
        number: numbers.Number = 2
        string: str = 3
        array: Sequence[JSON] = 4
        obj: Mapping[str, JSON] = 5

So, what would your code look like if json.loads returned one of these, instead of just returning a dict?

For the quick&dirty case, it would obviously be a whole lot more inconvenient to parse out a JSON than a plain dict. Today, you can already write:

    j = json.loads(s)
    j['aliases'][0]['first']

But if you want to specify a schema, map it to objects in your hierarchy, and validate it, that would be a huge pain with dynamically walking the structure, but comparatively easy treating JSON as an ADT:

    class Name((first: str, last: str)):
        def tojson(self):
            return JSON.object({'first': self.first, 'last': self.last})
        @classmethod
        def fromjson(cls, j):
            case j:
                of JSON.object as o:
                    return cls(o['first'], o['last'])
            raise ValueError('{} is not a name'.format(j))

    class Person((aliases: Sequence[Name], age: float)):
        def tojson(self):
            return JSON.object({'aliases': JSON.array(map(Name.tojson, self.aliases)), 'age': age})
        @classmethod
        def fromjson(cls, j):
            case j:
                of JSON.object as o:
                    case o['aliases']:
                        of JSON.array as a:
                            return cls([Name.fromjson(name) for name in a], o['age'])
            raise ValueError('{} is not a person'.format(j))

(Of course there's no reason Name and Person couldn't be "pure" ADTs, with free functions instead of methods, but it seems more Pythonic this way.)

This pattern matching syntax is nowhere near as simple as the ML or Haskell equivalent, which implies that maybe I didn't do as good a job with my straw-man syntax as I'd hoped. But note that a JSON parsing framework could automate all of that pattern matching based on the attributes and types of the class. Assuming I'd written such a thing, or found it on PyPI, or inherited it from the web framework I'm using, I could write the above as:

    class Name(JSONable[(first: str, last: str)]):
        pass

    class Person(JSONable[(aliases: Sequence[Name], age: float]):
        pass
So:

    person = Person.fromjson(json.loads(s))
    person['aliases'][0]['first']

This looks almost as simple as the non-validating case, but it will raise an exception if s doesn't actually specify a Person.

So, is that a good enough use case to include ADTs in Python?