[Python-3000] PEP 31XX: A Type Hierarchy for Numbers (and other algebraic entities)

[Jeffrey Yasskin]

On 4/25/07, Jim Jewett <jimjjewett at gmail.com> wrote:
> On 4/25/07, Jeffrey Yasskin <jyasskin at gmail.com> wrote:
> >     class MonoidUnderPlus(Abstract):
>
> Is this useful?  Just because two things are both Monoid instances
> doesn't mean I can add them -- they have to be part of the same
> Monoid.  By the time you do
>
>     assert isinstance(a, MonoidUnderPlus)
>     assert isinstance(b, MonoidUnderPlus)
>     assert isinstance(a, b.__class__) or isinstance(b, a.__class__)
>
> I'm not sure how much you've really saved.

I brought this up on the PEP 3119 thread, as an issue for
TotallyOrdered too. The exact syntax for checking that two objects are
"in the same instance of ABC X" should be decided there.

As to the benefits of MonoidUnderPlus over just hasattr(a,
'__plus__'), by knowing that the operation is associative, a function
may be able to speed itself up. A somewhat academic example is a
SortedList type:
  class SortedList(MonoidUnderPlus):
    def __init__(self, iterable): self.contents = sorted(iterable)
    def __add__(lhs, rhs): return merge(lhs, rhs)
Then (ignoring that sum currently requires numbers) we can define mysorted() as:
  def mysorted(iterable): return sum(map(SortedList, iterable)).contents
With sum() implemented as a simple for loop, this is insertion sort,
taking O(n^2) time. However, by noticing that + is associative on its
argument, sum can be defined (assume the annotation implies the
appropriate checking) roughly as:
  def sum(lst : SequenceOfMonoidUnderPlus):
    if len(lst) == 1: return lst[0]
    else: return sum(lst[:len(lst)//2]) + sum(lst[len(lst)//2+1:]
and we've transformed the algorithm into merge sort, taking O(n log n)
time. (Hm, the zero element isn't as useful here as in other languages
since you can't get a type without an instance. Maybe it should go
leave the interface.)

This optimization is, of course, incorrect if + is not associative.

> > **Open issue:** Do we want to give people a choice of which of the
> > following to define, or should we pick one arbitrarily?::
>
> >         def __neg__(self):
> >         def __sub__(self, other):
> Probably better to pick one

Will do.

-- 
Namasté,
Jeffrey Yasskin