[python] Generics/templates in python?

How does python handle generic/template type scenarios? Say I want to create an external file "BinaryTree.py" and have it handle binary trees, but for any data type.

So I could pass it the type of a custom object and have a binary tree of that object. How is this done in python?

This question is related to python templates generic-programming

The answer is


Python uses duck typing, so it doesn't need special syntax to handle multiple types.

If you're from a C++ background, you'll remember that, as long as the operations used in the template function/class are defined on some type T (at the syntax level), you can use that type T in the template.

So, basically, it works the same way:

  1. define a contract for the type of items you want to insert in the binary tree.
  2. document this contract (i.e. in the class documentation)
  3. implement the binary tree using only operations specified in the contract
  4. enjoy

You'll note however, that unless you write explicit type checking (which is usually discouraged), you won't be able to enforce that a binary tree contains only elements of the chosen type.


After coming up with some good thoughts on making generic types in python, I started looking for others who had the same idea, but I couldn't find any. So, here it is. I tried this out and it works well. It allows us to parameterize our types in python.

class List( type ):

    def __new__(type_ref, member_type):

        class List(list):

            def append(self, member):
                if not isinstance(member, member_type):
                    raise TypeError('Attempted to append a "{0}" to a "{1}" which only takes a "{2}"'.format(
                        type(member).__name__,
                        type(self).__name__,
                        member_type.__name__ 
                    ))

                    list.append(self, member)

        return List 

You can now derive types from this generic type.

class TestMember:
        pass

class TestList(List(TestMember)):

    def __init__(self):
        super().__init__()


test_list = TestList()
test_list.append(TestMember())
test_list.append('test') # This line will raise an exception

This solution is simplistic, and it does have it's limitations. Each time you create a generic type, it will create a new type. Thus, multiple classes inheriting List( str ) as a parent would be inheriting from two separate classes. To overcome this, you need to create a dict to store the various forms of the inner class and return the previous created inner class, rather than creating a new one. This would prevent duplicate types with the same parameters from being created. If interested, a more elegant solution can be made with decorators and/or metaclasses.


The other answers are totally fine:

  • One does not need a special syntax to support generics in Python
  • Python uses duck typing as pointed out by AndrĂ©.

However, if you still want a typed variant, there is a built-in solution since Python 3.5.

Generic classes:

from typing import TypeVar, Generic

T = TypeVar('T')

class Stack(Generic[T]):
    def __init__(self) -> None:
        # Create an empty list with items of type T
        self.items: List[T] = []

    def push(self, item: T) -> None:
        self.items.append(item)

    def pop(self) -> T:
        return self.items.pop()

    def empty(self) -> bool:
        return not self.items
# Construct an empty Stack[int] instance
stack = Stack[int]()
stack.push(2)
stack.pop()
stack.push('x')        # Type error

Generic functions:

from typing import TypeVar, Sequence

T = TypeVar('T')      # Declare type variable

def first(seq: Sequence[T]) -> T:
    return seq[0]

def last(seq: Sequence[T]) -> T:
    return seq[-1]


n = first([1, 2, 3])  # n has type int.

Reference: mypy documentation about generics.


If you using Python 2 or want to rewrite java code. Their is not real solution for this. Here is what I get working in a night: https://github.com/FlorianSteenbuck/python-generics I still get no compiler so you currently using it like that:

class A(GenericObject):
    def __init__(self, *args, **kwargs):
        GenericObject.__init__(self, [
            ['b',extends,int],
            ['a',extends,str],
            [0,extends,bool],
            ['T',extends,float]
        ], *args, **kwargs)

    def _init(self, c, a, b):
        print "success c="+str(c)+" a="+str(a)+" b="+str(b)

TODOs

  • Compiler
  • Get Generic Classes and Types working (For things like <? extends List<Number>>)
  • Add super support
  • Add ? support
  • Code Clean Up

Fortunately there has been some efforts for the generic programming in python . There is a library : generic

Here is the documentation for it: http://generic.readthedocs.org/en/latest/

It hasn't progress over years , but you can have a rough idea how to use & make your own library.

Cheers


Because Python is dynamically typed, the types of the objects don't matter in many cases. It's a better idea to accept anything.

To demonstrate what I mean, this tree class will accept anything for its two branches:

class BinaryTree:
    def __init__(self, left, right):
        self.left, self.right = left, right

And it could be used like this:

branch1 = BinaryTree(1,2)
myitem = MyClass()
branch2 = BinaryTree(myitem, None)
tree = BinaryTree(branch1, branch2)

Look at how the built-in containers do it. dict and list and so on contain heterogeneous elements of whatever types you like. If you define, say, an insert(val) function for your tree, it will at some point do something like node.value = val and Python will take care of the rest.


Here's a variant of this answer that uses metaclasses to avoid the messy syntax, and use the typing-style List[int] syntax:

class template(type):
    def __new__(metacls, f):
        cls = type.__new__(metacls, f.__name__, (), {
            '_f': f,
            '__qualname__': f.__qualname__,
            '__module__': f.__module__,
            '__doc__': f.__doc__
        })
        cls.__instances = {}
        return cls

    def __init__(cls, f):  # only needed in 3.5 and below
        pass

    def __getitem__(cls, item):
        if not isinstance(item, tuple):
            item = (item,)
        try:
            return cls.__instances[item]
        except KeyError:
            cls.__instances[item] = c = cls._f(*item)
            item_repr = '[' + ', '.join(repr(i) for i in item) + ']'
            c.__name__ = cls.__name__ + item_repr
            c.__qualname__ = cls.__qualname__ + item_repr
            c.__template__ = cls
            return c

    def __subclasscheck__(cls, subclass):
        for c in subclass.mro():
            if getattr(c, '__template__', None) == cls:
                return True
        return False

    def __instancecheck__(cls, instance):
        return cls.__subclasscheck__(type(instance))

    def __repr__(cls):
        import inspect
        return '<template {!r}>'.format('{}.{}[{}]'.format(
            cls.__module__, cls.__qualname__, str(inspect.signature(cls._f))[1:-1]
        ))

With this new metaclass, we can rewrite the example in the answer I link to as:

@template
def List(member_type):
    class List(list):
        def append(self, member):
            if not isinstance(member, member_type):
                raise TypeError('Attempted to append a "{0}" to a "{1}" which only takes a "{2}"'.format(
                    type(member).__name__,
                    type(self).__name__,
                    member_type.__name__ 
                ))

                list.append(self, member)
    return List

l = List[int]()
l.append(1)  # ok
l.append("one")  # error

This approach has some nice benefits

print(List)  # <template '__main__.List[member_type]'>
print(List[int])  # <class '__main__.List[<class 'int'>, 10]'>
assert List[int] is List[int]
assert issubclass(List[int], List)  # True

Actually now you can use generics in Python 3.5+. See PEP-484 and typing module documentation.

According to my practice it is not very seamless and clear especially for those who are familiar with Java Generics, but still usable.


Since python is dynamically typed, this is super easy. In fact, you'd have to do extra work for your BinaryTree class not to work with any data type.

For example, if you want the key values which are used to place the object in the tree available within the object from a method like key() you just call key() on the objects. For example:

class BinaryTree(object):

    def insert(self, object_to_insert):
        key = object_to_insert.key()

Note that you never need to define what kind of class object_to_insert is. So long as it has a key() method, it will work.

The exception is if you want it to work with basic data types like strings or integers. You'll have to wrap them in a class to get them to work with your generic BinaryTree. If that sounds too heavy weight and you want the extra efficiency of actually just storing strings, sorry, that's not what Python is good at.