On PEP 322 (ireverse)

**Alex Martelli** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

Gonçalo Rodrigues wrote:
[color=blue]
> I've lost the original thread on my news reader so I'm opening a new
> one.
>
> First, i like the name ireverse, much better then inreverse (eek!).[/color]

I still prefer Werner Schiendl's idea of iter.reversed, IF we find a
way to have builtin function iter grow a 'staticmethod' of sorts...!

[color=blue]
> Just a simple comment/question:
>
> - Why a builtin function? Why not just stuff it in the itertools[/color]

It's inappropriate for itertools according to detailed criteria that
Raymond has recently posted here.
[color=blue]
> module? The builtins is already fat as it is, making it fatter is not[/color]

Yes, builtins should indeed be reserved strictly for the indispensable
cases (and trimmed a LOT in 3.0 -- but that's years away). Which is
why, e.g., list.sorted was made a classmethod of type list, rather
than a built-in. Similarly, IF iter was a type, iter.reversed would
be the "one obvious way to do it"...

Alex

**Raymond Hettinger** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

> Gonçalo Rodrigues wrote:[color=blue][color=green]
> > First, i like the name ireverse, much better then inreverse (eek!).[/color][/color]

Thanks.

[Alex][color=blue]
> I still prefer Werner Schiendl's idea of iter.reversed, IF we find a
> way to have builtin function iter grow a 'staticmethod' of sorts...![/color]

No thanks. Yuck. Please do not twist this simple idea into knots.
This is supposed to be something you can teach in the first half-hour
and then use forever. I would sooner teach negative xrange()
indices than immediately launch into dotted references to a static
method attached to something that doesn't look like it should have
a method. This is a simplification, not an exercise in being cute
or clever just to avoid a builtin.

Raymond Hettinger

**Terry Reedy** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

"Alex Martelli" <aleax@aleax.it > wrote in message
news:4xQnb.3738 12$R32.12367046 @news2.tin.it.. .[color=blue]
> Gonçalo Rodrigues wrote:[color=green]
> > First, i like the name ireverse, much better then inreverse[/color][/color]
(eek!).[color=blue]
>
> I still prefer Werner Schiendl's idea of iter.reversed, IF we find a
> way to have builtin function iter grow a 'staticmethod' of sorts...![/color]

As I suggested elsewhere, make iter() the type object for iterator.
Then iter.reversed is closely parallel to list.sorted.
[color=blue]
> Which is
> why, e.g., list.sorted was made a classmethod of type list, rather
> than a built-in. Similarly, IF iter was a type, iter.reversed would
> be the "one obvious way to do it"...[/color]

Any good reason not to make iter so? int, str, and float were once
bifs also. I'm +1 on iter.reversed, along with list.sorted.

Terry J. Reedy

**Roy Smith** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

"Terry Reedy" <tjreedy@udel.e du> wrote:[color=blue]
> As I suggested elsewhere, make iter() the type object for iterator.
> Then iter.reversed is closely parallel to list.sorted.[/color]

I've got a question about list.sorted. I assume it's just a list that's
initialized to have its elements sorted when it's created? We're not
talking about some new magic container type which keeps its elements
sorted all the time?

In other words, I'm assuming that

l = list.sorted ((1, 2, 5, 3))
l.append (4)
print l

will print [1, 2, 3, 5, 4], right?

**Michael Hudson** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

"Terry Reedy" <tjreedy@udel.e du> writes:
[color=blue]
> "Alex Martelli" <aleax@aleax.it > wrote in message
> news:4xQnb.3738 12$R32.12367046 @news2.tin.it.. .[color=green]
> > Gonçalo Rodrigues wrote:[color=darkred]
> > > First, i like the name ireverse, much better then inreverse[/color][/color]
> (eek!).[color=green]
> >
> > I still prefer Werner Schiendl's idea of iter.reversed, IF we find a
> > way to have builtin function iter grow a 'staticmethod' of sorts...![/color]
>
> As I suggested elsewhere, make iter() the type object for iterator.[/color]

The what?

Cheers,
mwh

--
it's not that perl programmers are idiots, it's that the language
rewards idiotic behavior in a way that no other language or tool
has ever done -- Erik Naggum, comp.lang.lisp

**Terry Reedy** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

"Roy Smith" <roy@panix.co m> wrote in message
news:roy-47C5A5.12101629 102003@reader2. panix.com...[color=blue]
> "Terry Reedy" <tjreedy@udel.e du> wrote:[color=green]
> > As I suggested elsewhere, make iter() the type object for[/color][/color]
iterator.[color=blue][color=green]
> > Then iter.reversed is closely parallel to list.sorted.[/color]
>
> I've got a question about list.sorted. I assume it's just a list[/color]
that's[color=blue]
> initialized to have its elements sorted when it's created?[/color]

Correct: As I understand it,
l=list.sorted(i terable) == l=list(iterable ); l.sort

tjr

**Raymond Hettinger** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

[Terry Reedy][color=blue]
> Any good reason not to make iter so? int, str, and float were once
> bifs also.[/color]

The C code for it has a split path, calling __iter__ for objects that
have it, building iterator wrappers for sequences that don't have
__iter__, or building another wrapper when the inputs are a
function and sentinel. IOW, it is a factory function capable
of constructor any of several different types.
[color=blue]
> I'm +1 on iter.reversed, along with list.sorted.[/color]

Please no.

list.sorted() is entirely unrelated. It is attached to lists because that
is what it generally returns and because its functionality is closely
tied to list.sort(). It is a class method because that gave it
richer functionality by taking any iterable as an argument:

list.sorted('a string').

When I posted the PEP for comment, I was looking for confirmation
that the underlying problem is real and for folks to look through their
own code to see if the proposed solution truly offered improvements
in terms of clarity and performance.

Grafting this onto iter is not an option; I would rather lose the
functionality than have the experts here twist it into something
I can't easily explain to a client.

Raymond Hettinger

**Terry Reedy** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

"Raymond Hettinger" <vze4rx4y@veriz on.net> wrote in message
news:YSSnb.2968 3$4O1.16000@nwr dny01.gnilink.n et...[color=blue]
> [Terry Reedy][color=green]
> > Any good reason not to make iter so? int, str, and float were[/color][/color]
once[color=blue][color=green]
> > bifs also.[/color]
>
> The C code for it has a split path, calling __iter__ for objects[/color]
that[color=blue]
> have it, building iterator wrappers for sequences that don't have
> __iter__, or building another wrapper when the inputs are a
> function and sentinel. IOW, it is a factory function capable
> of constructor any of several different types.[/color]

Good reason acknowledged.
[color=blue][color=green]
> > I'm +1 on iter.reversed,[/color][/color]

rescinded.

tjr

**Paul Moore** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

"Raymond Hettinger" <vze4rx4y@veriz on.net> writes:
[color=blue]
> [Alex][color=green]
>> I still prefer Werner Schiendl's idea of iter.reversed, IF we find a
>> way to have builtin function iter grow a 'staticmethod' of sorts...![/color]
>
> No thanks. Yuck. Please do not twist this simple idea into knots.[/color]

[...]
[color=blue]
> This is a simplification, not an exercise in being cute
> or clever just to avoid a builtin.[/color]

Agreed. Keep it simple. For a name, I'd go for ireverse() if reverse()
is not possible. But not inreverse()...

Paul
--
This signature intentionally left blank

**Fredrik Lundh** · Jul 18 '05, 04:34 AM

Re: On PEP 322 (ireverse)

Raymond Hettinger wrote:
[color=blue]
> When I posted the PEP for comment, I was looking for confirmation
> that the underlying problem is real[/color]

well, I've never felt any need for a function that makes it impossible
to reverse a sequence...

(I think the correct form is "irreversib le", by the way. I'm not sure
"irreverse" is a real word...)

</F>

**Alex Martelli** · Jul 18 '05, 04:34 AM

alwayssortedlis t (was Re: On PEP 322 (ireverse))

Roy Smith wrote:
[color=blue]
> "Terry Reedy" <tjreedy@udel.e du> wrote:[color=green]
>> As I suggested elsewhere, make iter() the type object for iterator.
>> Then iter.reversed is closely parallel to list.sorted.[/color]
>
> I've got a question about list.sorted. I assume it's just a list that's
> initialized to have its elements sorted when it's created? We're not
> talking about some new magic container type which keeps its elements
> sorted all the time?
>
> In other words, I'm assuming that
>
> l = list.sorted ((1, 2, 5, 3))
> l.append (4)
> print l
>
> will print [1, 2, 3, 5, 4], right?[/color]

Perfectly right. If you DO want a listoid container that keeps its
elements sorted, that's not hard to make for yourself. There are
basically two obvious implementation strategies:
-- ensure the underlying list is re-sorted at each insertion,
append &c, and/or
-- let the underlying list grow as it will on insertion &c, but
make sure it's sorted at any method that accesses it (you can
use a flag -- 'have there being any append/insert/... since
the last sort?' -- to re-sort only when needed).

I'll choose the first for general use because:
-- accesses are much more frequent than modifications,
-- list.sort is VERY fast when a list is "nearly sorted"
-- the second approach would require sorting also on many
kind of changes (e.g. __setitem__ -- to ensure the items
being replaced ARE those the user expects...)
&c.

So, we clearly start with:

class alwayssortedlis t(list):

def __init__(self, *args):
list.__init__(s elf, *args)
self.sort()

We need to ensure sorting at creation. We _might_ make the sort
method in this class a noop and call list.sort(self) instead,
but, naah -- list.sort is SO fast when called on an already
sorted list that it ain't even funny, so, choose simplicity.
Onwards to simple mods:

def append(self, *args):
list.append(sel f, *args)
self.sort()

def __setitem__(sel f, *args):
list.__setitem_ _(self, *args)
self.sort()

....starting to see a pattern, by any chance...?-) Yep, ALL
list mutators we _need_ to override are exactly like this!
(We MAY override e.g. index and remove to take advantage
of the sortedness, but, that's optional...:-). extend and
insert too (now, reverse IS an interesting issue...!-), and
__iadd__ and __imul__ (methods creating new lists, such as
__add__, __mul__ and __rmul__, are slightly different). Oh,
__setslice__, too.

Well, doing it in longhand is fine, of course, but why not
have a bit more fun with (not showing the __add__ &c):

class solist(list): pass

def solist_method(m ethname):
list_method = getattr(list, methname)
def method(self, *args):
list_method(sel f, *args)
self.sort()
setattr(solist, methname, method)
for n in 'init setitem iadd imul'.split:
solist_method(' __%s__' % n)
for n in 'append extend insert'.split:
solist_method(' %s' % n)

Not much shorter than the boilerplate/longhand, and not
perfect (we should make a new function object to give it
the right func_name -- as is, all the methods' names
will be "method" in tracebacks &c...:-), but sorta fun.

Testing & completion left as an exercise to the student...

Alex

**Raymond Hettinger** · Jul 18 '05, 04:35 AM

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

[Alex Martelli][color=blue]
> Perfectly right. If you DO want a listoid container that keeps its
> elements sorted, that's not hard to make for yourself. There are
> basically two obvious implementation strategies:
> -- ensure the underlying list is re-sorted at each insertion,
> append &c, and/or
> -- let the underlying list grow as it will on insertion &c, but
> make sure it's sorted at any method that accesses it (you can
> use a flag -- 'have there being any append/insert/... since
> the last sort?' -- to re-sort only when needed).
>
> I'll choose the first for general use because:
> -- accesses are much more frequent than modifications,
> -- list.sort is VERY fast when a list is "nearly sorted"[/color]

That could also be an argument for the second approach.
The timsort excels at finding the unsorted part, sorting it,
and merging it with rest. And, if there were any partial
ordering of the unsorted part, it tends to take advantage
of that.

For the second approach, I would keep a sorted flag.
Whenever a new element is added the flag would be
set to False. Upon data access, a False flag indicates
a need to run sort() and then the flag is set to True.
IOW, sort only when needed and sort as many items
at a time as you can.

Raymond Hettinger

**Jeremy Fincher** · Jul 18 '05, 04:35 AM

Re: On PEP 322 (ireverse)

Is there any reason this PEP is of so limited scope? Why not a more
comprehensive PEP defining a reverse iteration protocol similar the
protocol we have now for forward iteration?

It just seems that if this is implemented as-is, it'll be one of those
warts left around when Python gets a reverse (or even more general)
iteration protocol that will almost certainly operate in a different
manner. It just seems to be fodder for supercession.

Jeremy

**Bengt Richter** · Jul 18 '05, 04:35 AM

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

On Wed, 29 Oct 2003 20:12:23 GMT, Alex Martelli <aleax@aleax.it > wrote:
[color=blue]
>Roy Smith wrote:
>[color=green]
>> "Terry Reedy" <tjreedy@udel.e du> wrote:[color=darkred]
>>> As I suggested elsewhere, make iter() the type object for iterator.
>>> Then iter.reversed is closely parallel to list.sorted.[/color]
>>
>> I've got a question about list.sorted. I assume it's just a list that's
>> initialized to have its elements sorted when it's created? We're not
>> talking about some new magic container type which keeps its elements
>> sorted all the time?
>>
>> In other words, I'm assuming that
>>
>> l = list.sorted ((1, 2, 5, 3))
>> l.append (4)
>> print l
>>
>> will print [1, 2, 3, 5, 4], right?[/color]
>
>Perfectly right. If you DO want a listoid container that keeps its
>elements sorted, that's not hard to make for yourself. There are
>basically two obvious implementation strategies:
> -- ensure the underlying list is re-sorted at each insertion,
> append &c, and/or
> -- let the underlying list grow as it will on insertion &c, but
> make sure it's sorted at any method that accesses it (you can
> use a flag -- 'have there being any append/insert/... since
> the last sort?' -- to re-sort only when needed).
>
>I'll choose the first for general use because:
> -- accesses are much more frequent than modifications,
> -- list.sort is VERY fast when a list is "nearly sorted"
> -- the second approach would require sorting also on many
> kind of changes (e.g. __setitem__ -- to ensure the items
> being replaced ARE those the user expects...)
>&c.
>[/color]
[...]

No comments on the heapq module?

Regards,
Bengt Richter

On PEP 322 (ireverse)

On PEP 322 (ireverse)

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment