Better alternative for algebraic data types

[JukkaL]

Many languages support algebraic data types, including Haskell, OCaml, Scala, Swift and Rust. Many programmers like them and they have some benefits over Python subclassing, which I won't discuss in detail here.

Currently we can kind of fake algebraic data types by using union types and named tuples:

class Circle:
    radius: float

class Rectangle:
    width: float
    height: float

Shape = Union[Circle, Rectangle]

def area(s: Shape) -> float:
    if isinstance(s, Circle):
        result = math.pi * s.radius**2
    elif isinstance(s, Rectangle):
        result = s.width * s.height
    return result

There are a few problems with this currently:

1. If you forget to handle a case, mypy often won't complain about this. Catching these errors is often mentioned as one of the nicest things about algebraic data types.
2. You need to write each item type name twice, once in the class definition and once in the union type definition. This is somewhat error-prone.
3. The union type definition needs to come after the item types, which feels backwards to me. (If we fixed forward references to types in type aliases, it might help a bit.)
4. Mypy doesn't keep track of the name of the union type alias internally, and in error messages it will just print out the entire union. This could be awkward since the union can have many items.

For (1), mypy could detect at least some undefined variables and recognize (some) if statements used for "pattern matching". For example, assume that we added a new shape, Triangle. Now mypy should complain about area(), as it fails to handle triangles (if we'd have used multiple returns, mypy could already have caught the error):

def area(s: Shape) -> float:
    if isinstance(s, Circle):
        result = math.pi * s.radius**2
    elif isinstance(s, Rectangle):
        result = s.width * s.height
    return result   # Error: "result" may be undefined (union item "Triangle" not handled)

For (2), (3) and (4), we could have some new syntax:

from mypy_extensions import NamedTupleUnion

class Shape(NamedTupleUnion):  # This would be roughly similar to original union type
    pass

class Circle(Shape):
    radius: float

class Rectangle(Shape):
    width: float
    height: float

NamedTupleUnion would have a few special features. All subclasses are named tuples and must be defined in the same module as the NamedTupleUnion type (i.e. it can't be extended outside the current module). This way we can check whether all item types are handled using isinstance checks. Finally, only one level of inheritance would be supported, for simplicity -- though I'm not sure if this restriction is necessary.

[This is just a random idea I wanted to write down and it's not urgent in any way.]

[ilevkivskyi]

This is an interesting idea. Here is some early bikeshedding:

• What about calling this a TaggedUnion?
• What about using a (more Enum-like) nested class syntax:

class Shape(TaggedUnion):
    class Circle:
        radius: float

    class Rectangle:
        width: float
        height: float

EDIT: Fixed typo pointed by @kirbyfan64

[refi64]

What about using a (more Enum-like) nested class syntax:

But isn't Shape undefined for the duration of its body evaluation?

On topic: +10000 to this. ADTs are awesome. :D

[ilevkivskyi]

But isn't Shape undefined for the duration of its body evaluation?

Ah, sorry, that is just a typo, it is not needed.

[JukkaL]

What about calling this a TaggedUnion?

Hmm.. it would be less clear that the subclasses are named tuples (we want the default __init__, unpacking, etc.). Also, there wouldn't be any extra tags required for these unions, as all objects have a type 'tag' by default. But I agree that the name NamedTupleUnion isn't exactly pretty.

What about using a (more Enum-like) nested class syntax:

This would require using qualified names such as Shape.Circle in isinstance tests, which would be somewhat clumsy.

[ilevkivskyi]

This would require using qualified names such as Shape.Circle in isinstance tests, which would be somewhat clumsy.

This is true. On the other hand the definition is a bit more compact, and it is immediately visible later in code that Circle is a member of Shape union.

But I agree that the name NamedTupleUnion isn't exactly pretty

NamedUnion is a bit shorter and reminds NamedTuple. Also there will be a parallel: Union and Tuple vs. NamedUnion and NamedTuple.

[elazarg]

I would have liked the enum-like syntax (I have suggested it some time ago) but it is not exactly a tagged union, since Shape.Circle is not Shape, and sadly the syntax does not allow subclassing.

Here's a wild idea:

with NamedUnion as Shape:
    class Circle(Shape):
        radius : float

    class Rectangle(Shape):
        width: float
        height: float

This way we have a bounded scope for the definition of subelements of Shape, and we can also use its name in the subclasses.

[datnamer]

Please excuse the noob question, but how would this be different than the classes extending the Shape protocol or abstract class?

[elazarg]

The point is the declaration "A Shape must be one of these types and nothing else" in a way that can be used by mypy (using the declaration syntax) and checked at runtime (using isinstance() to distinguish between items).

[ilevkivskyi]

Just another idea for the possible syntax. If we allow only named tuples a s members, then one can write:

class Shape(NamedUnion):
    Circle: {radius: int}
    Rectangle: {width: int, height: int}

At runtime, this will be transformed so that Shape.Circle will be a NamedTuple. As well __bases__ could be patched so that issubclass(Shape.Circle, Shape) will return True. Also some other facilities could be added, making NamedUnion a more advanced version of Enum.

[grayfall]

@elazarg I really like your syntax proposition. It can also be used to mimic Haskell's type constraints:

with NamedUnion['Shape', constraints] as Shape:
    class Circle(Shape):
        radius : float

    class Rectangle(Shape):
        width: float
        height: float

NamedUnion[name, constraints] resembles TypeVar call signature. We can actually subclass from constraints to further mimic Haskell's deriving:

class NamedUnion(...):
    ...
    def __class_getitem__(cls, params):
        name, constraints = params
        class T(*constraints):
            pass
        
        T.__name__ = name
        T.__qualname__ = name
        return T