Description

A simple implementation of Algebraic Data Types in Python following the same shape as the enums in the standard library.

Usage

Import the AlgebraicEnum from the algebraicenum package and define your ADTs the same way you would define an Enum. The difference to enums is that ADTs expect a tuple of types on the right hand side.

Example

Here is an example AlgebraicEnum:

from adt import AlgebraicEnum

class Shape(AlgebraicEnum):
    Rectangle = (int, int)
    Circle = int
    Triangle = (int, int)
    Empty = ()

As you can see, if the type only has a single value in the constructor, you can define the type without tuple syntax.

If a type does not accept any arguments you can define it using an empty tuple ().

Instantiating

You can instantiate your ADTs by simply calling their constructor from their base class.

print(Shape.Rectangle(1, 2)) # Shape.Rectangle(1, 2)
print(Shape.Circle(3)) # Shape.Circle(3)
print(Shape.Triangle(4, 5)) # Shape.Triangle(4, 5)
print(Shape.Empty()) # Shape.Empty()

Subtypes

All expressions of your ADT are subclasses of the base class and their own.

print(isinstance(Shape.Circle(3), Shape)) # True
print(isinstance(Shape.Circle(3), Shape.Circle)) # True
print(isinstance(Shape.Circle(3), Shape.Triangle)) # False

Sub types with named members

You can not only use tuples to declare the constructor of the subtypes, but also a dictionary. Using a dictionary allows addressing the members by a name. As a result, there are four different ways to define a subtype.

1. By using a tuple with the unnamed argument types as elements.
2. If the constructor only contains a single type, it can be used directly.
3. An empty tuple specifies types without arguments.
4. A dictionary specifies types with named members.

class Shape(AlgebraicEnum):
    Rectangle = { 'width': int, 'height': int }
    Circle = int
    Triangle = { 'base': int, 'height': int }
    Empty = ()

    def area(self) -> float:
        if isinstance(self, Shape.Rectangle):
            return self.width * self.height
        if isinstance(self, Shape.Circle):
            import math
            return math.pi*self[0]**2
        if isinstance(self, Shape.Triangle):
            return self.base * self.height / 2
        assert isinstance(self, Shape.Empty)
        return 0

print(Shape.Rectangle(width=2, height=3).area()) # 6
print(Shape.Circle(4).area()) # 50.27
print(Shape.Triangle(base=5, height=6).area()) # 15
print(Shape.Empty().area()) # 0

Recursive types

Recursive types are created by specifying the path to the type or by using the special Self object from the algebraicenum package.

class Tree(AlgebraicEnum):
    Node = (Self, '__main__.Tree')
    Leaf = int

tree = Tree.Node(
    Tree.Leaf(1),
    Tree.Node(
        Tree.Leaf(2),
        Tree.Leaf(3)))

Shared methods

You can define methods for your ADT that are shared by all expressions. For example, you can define a find() function for a binary search tree that returns the subtree that contains the specified value.

class BinarySearchTree(AlgebraicEnum):
    Node = (Self, int, Self)
    Leaf = int

    def find(self, value: int):
        if isinstance(self, BinarySearchTree.Node):
            if value < self[1]:
                return self[0].find(value)
            elif value > self[1]:
                return self[2].find(value)
            return self
        elif isinstance(self, BinarySearchTree.Leaf) and self[0] == value:
            return self
        else:
            raise ValueError(value)


subtree = BinarySearchTree.Node(BinarySearchTree.Leaf(5), 6, BinarySearchTree.Leaf(7))
tree = BinarySearchTree.Node(BinarySearchTree.Leaf(3), 4, subtree)

print(tree.find(4) is tree) # True
print(tree.find(3) is tree[0]) # True
print(tree.find(6) is subtree) # True
print(tree.find(5) is subtree[0]) # True
print(tree.find(7) is subtree[2]) # True
# tree.find(8) # Raises: ValueError(8)