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,))
But notice that a tagged union of plain (named) tuples is exactly equivalent to an untagged union of records. You could just as well write that type as:
(Success(headers: Sequence[str], body: Iterable[str])
| Failure(code: int, description: str, headers: Sequence[str], body: Iterable[str])
| Error(errno: int,))
Either way, a language could allow you to dissect unions with the same member syntax used by records. But the latter allows you to dissect them by pattern matching, or sometimes just by comparison, which is often much simpler.
| Failure(code: int, description: str, headers: Sequence[str], body: Iterable[str])
| Error(errno: int,))
Either way, a language could allow you to dissect unions with the same member syntax used by records. But the latter allows you to dissect them by pattern matching, or sometimes just by comparison, which is often much simpler.
In practice
Most languages that make heavy use of ADTs go with a sort of hybrid: the tags are part of the named record type, but named record types can only be defined inside sum types, and therefore it doesn't really matter.
For example, here's how cons lists are generally defined:
List(Cons(head: T, tail: List[T]) | Nil())
Here Cons and Nil are called constructors for List. Whichever way you interpret this, Nil() is an instance of type Nil (or of the Nil kind of type List), and also an instance of type List.* Cons(1, Nil()) is an instance of type Cons[int] (or the Cons kind of type List[int]), and also an instance of type List[int].
However, this does raise a question of namespacing: is the name Cons available in the same scope as List, or do you have to write Cons.List? (It's not a coincidence that this same question that comes up with enum in many languages, which I'll get to later.)
* It's worth noting that in most ADT-based languages, this Nil() can have a type, like List[int]; the fact that it isn't always inferable just means that sometimes you have to specify it explicitly.
Optional/Maybe
One special case that people often propose for Python isn't really special at all.
A value that can be either an int or None is just int | NoneType.
A value that can be either an int or None, with the type tagged by a name, is (Just(int) | Nothing(NoneType)).*
In languages that make sum types very concise, like Haskell,** it's perfectly reasonable to write Maybe int as a type, and Just 42 or Nothing as values of that type, and to pattern match the value as Just n | Nothing.
Many other languages add syntactic sugar: int? means Maybe[int], n! means the value of n or raise an exception if it's Nothing, n? means nil-chaining (an expression with n? has the value of the expression with the Just value if n is not Nothing, or it has the value Nothing if n is Nothing), there may be shortcut values to extract a value (e.g., Swift's "if let n: int = m {} else {}", and so on. But under the covers, these are all doing things that can be expressed directly in terms of the sum type.
* Note that the direct mapping of Haskell's Maybe to Python would be (Just(int,) | Nothing()). But because Python's unions aren't mathematical product types, and NoneType isn't a real unit type, as described earlier, it's more convenient to tag non-record-typed values in the Maybe, and there's really no theoretical reason you can't do that, it just means either treating the tags are part of the union rather than part of a record constructor, or a bit of extra syntactic sugar.
** In Haskell, tags are available in the outer namespace, and type parameters and constructors, like functions, don't need parentheses around their arguments.
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__
A class with __slots__ is also pretty close to a named record type, and in some ways seems like a better fit, assuming we had a syntax to type the slots, which seems pretty easy.
However, the fact that, unlike a namedtuple, it's not a tuple is at least a theoretical problem, if not a practical one. The fact that there is nothing requiring the constructor arguments to map to the slots is a bigger problem. And it's hard to imagine a way to write these anonymously and inline (short of some kind of horrible expression using the type class's constructor).
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
>>> barcode = Barcode.UPCA(8, 85909, 51226, 3)
>>> barcode
<Barcode.UPCA(LL: 8, L: 85909, R: 51226, RR: 3): 1>
>>> barcode.LL
8
Of course you still need isinstance, pattern matching, or EAFP code to distinguish whether you've got a UPCA or a QRCode:
>>> barcode = Barcode.QRCode('ABCDEFGHIJKLMNOP')
>>> barcode.LL
AttributeError: 'Barcode.QRCode' object has no attribute 'LL'
>>> barcode
But still, it looks a lot prettier than using Union.
What about recursion?
One of the important features of ADTs is that they can be recursive. See the List example above: the second element of a Cons is a List.
In Python, this means we either need some kind of explicit forward reference (as used by MyPy), or a way to define sum types and record types in such a way that they can automatically use the type being defined.
Notice that it's relatively easy to write an "auto-numbered" Enum class that doesn't require you to specify a value; referencing an unknown name just gives it the next number in sequence and binds it. With a slightly smarter/hackier metaclass, I believe you could also write an "auto-recursive" Enum that assumes any unknown name is the class itself, and then checks at construction time that the only unknown name seen was the class name. I haven't actually tried to do this, but I'm going to just naively assume it's possible; if not, something like MyPy's forward references may be necessary.
So ADTs are just a subset of classes?
Each namedtuple type is a class, and each Enum type is a class, and I've defined ADTs in terms of (implicit) namedtuples and Enums. This seems at first to go against the spirit of ADTs, which are a completely alternative form of typing to OO classes.
But note that in Python, tuple is a class, int is a class, NonteType is a class, every type is a class.
More importantly, ADTs are a strict subset of classes. The "strict subset" part is what makes them useful: they have a static structure, they have
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
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?
View comments