python Generic Type Hints + user-defined container + constraining to Types implementing __add__ method

Question

I want to implement in python 3.8 a Liste class the Lisp way with head and tail, car(), cdr() and nil. I want to define a generic type accepting objects of Type T in the Liste.

from __future__ import annotations
from typing import TypeVar, Callable, Generic

T = TypeVar('T')
class Liste(Generic[T]):

    def __init__(self, h: T, t: Liste[T]) -> None:
        self.head = h
        self.tail = t

    @staticmethod
    def nil() -> Liste[T]:
        return Liste(None, None)

    def est_vide(self) -> bool:
        return (self.head is None) and (self.tail is None)
    def cdr(self)->Liste[T]:
        if self.tail is None: return Liste.nil()
        else: return  self.tail

    def sum(self)->T:
        if self.est_vide():
            return 0
        else:
            return self.head + self.cdr().sum()

I had a very good moment with type hints all along. But mypy points 4 errors

liste_sof.py:13: error: Argument 1 to "Liste" has incompatible type "None"; expected "T"
liste_sof.py:13: error: Argument 2 to "Liste" has incompatible type "None"; expected "Liste[T]"
liste_sof.py:23: error: Incompatible return value type (got "int", expected "T")
liste_sof.py:25: error: Unsupported left operand type for + ("T")
Found 4 errors in 1 file (checked 1 source file)

Problem 1 is to be able to specify that I expect T objects that implement the __add__ method. I don't know how to do that.

Problem 2 is to deal with the special Liste.nil() empty object of my class.

Answer 1

Mypy is complaining because you need to use Optional if you want h or t to be able to be None, otherwise, you are implying everything must be None, which isn't generic.

You can use structural typing with a Protocol to express "has __add__".

Finally, there is no clean way to get "the empty object". For built-in types, type(self)() may work, but honestly, I would just force the API take the initial value.

from __future__ import annotations
from typing import TypeVar, Callable, Generic, Protocol, Optional


T = TypeVar('T')

class SupportsAdd(Protocol[T]):
    def __add__(self: T, other: T) -> T:
        ...

A = TypeVar('A', bound=SupportsAdd)

class Liste(Generic[A]):
    def __init__(self, h: Optional[A], t: Optional[Liste[A]]) -> None:
        self.head = h
        self.tail = t

    @staticmethod
    def nil() -> Liste[A]:
        return Liste(None, None)

    def est_vide(self) -> bool:
        return (self.head is None) and (self.tail is None)

    def cdr(self)->Liste[A]:
        if self.tail is None: return Liste.nil()
        else: return  self.tail

    def sum(self, init: A) -> A:
        if self.head is None or self.tail is None:
            return init
        else:
            return self.head + self.cdr().sum(init)

As I stated in the comments, this class is very academic, you probably shouldn't actually use it. It will be inefficient. At the very least, you shouldn't use recursion for sum.