Sorted Returns List and Reversed Returns Iterator

[Terry Reedy]

Peter Otten wrote:
> ++imanshu wrote:

>> I agree. Iterator is more flexible.

I disagree.  Neither is more flexible.  You can iter the list returned 
by sorted and list the iter returned by reversed.  Both do the minimum 
work necessary.  See below.

 > Together and both might have returned the same types.

True, but only by doing potentially unnecessary work and requiring the 
caller to do potentially unnecessary work that might even prevent the 
program from working.  This is less flexible.

Suppose sorted now returns alist with 50 million items.  Suppose it 
instead returned iter(alist) but the caller wants to randomly index the 
items.  Since the caller could not access the existing 50 million item 
list, the caller would have to make another 50 million item copy.  This 
is non-trivial and might not even work do to memory limitations.

> It's easy to generate a reversed sequence on the fly but impractical for a
> sorted one. Python is taking the pragmatic approach here.

To expand on this: sorting and reversing are algorithmically different 
operations.   Sorting requires that one have all items in hand in a 
mutable sequence (list) for arbitrary re-ordering.  Sorted works on any 
iterable and starts by making a new list.  There is no point to not 
returning that list after it is sorted.  It would be more work and less 
useful to do more.

sorted(iterable, key=None, reverse=False):
   newlist = list(iterable)
   newlist.sort(key, reverse)
   return newlist

Iterating over a concrete sequence in reverse order, on the other hand, 
is trivial.  It would be more work and less useful to do more.

def _reversed(seq): # 'hidden' generator function
   n = len(seq)
   while n:
     n -= 1
     yield seq[n]

def reversed(seq):
   if hasattr(seq, '__reversed__'):
     return seq.__reversed__() # I presume this is tried first
   else:
     return _reversed(seq) # generic fall-back

Terry Jan Reedy