[Python-ideas] Adding collections.abc.Ordered

[Steven D'Aprano]

On Sat, Dec 26, 2015 at 07:11:59PM -0600, Wes Turner wrote:

> * collections.abc.Ordered
> * collections.abc.Reversible
> * collections.abc.Infinite [...]
> 
> * collections.abc.Sorted ?
> * collections.abc.Recursive ?
> 
> Rationale:
> 
> These are all attributes of collections that would allow us to reason about
> [complexity, types, runtime]?

Rather than vague abstractions like "reason about complexity", can we 
have some concrete use-cases for these?

"Sorted" is not strictly property of the collection alone, it is a 
property of the collection, the item in the collection, and a sorting 
function. The collection cannot be Sorted unless the items themselves 
are Sortable, which is clearly a property of the items, not the 
collection; and whether or not the collection actually is sorted or not 
depends on what you are sorting by.

So ["apple", "bear", "cat", "do"] may or may not be sorted. If you mean 
"sorted in dictionary order", it is, but if you mean "sorted by the 
length of the word", it most certainly is not. If abc.Sorted only 
considers the default sort order, it will be useless for many purposes.

Just this morning I was writing some code where I needed a sequence of 
2-tuples sorted in reverse order (highest to lowest) by the second item 
and by the length of the first item, in that order. For my purposes, 
this list would count as Sorted:

[("dog", 9.2), ("apple", 7.5), ("aardvark", 7.5), ("dog", 4.1)]

How does your abc.Sorted help me?



> [While someone is at it, annotating functions and methods with complexity
> class URI fragments accessible at runtime could also be useful for [dynamic
> programming].]

I'm afraid I don't understand what you mean by "complexity class URI 
fragments", or why they would be useful for dynamic programming.



> * Ordered is justified by this thread
> * Reversible is distinct from Ordered (because Infinite sequences)
> * Infinite is the distinction between Ordered and Reversible

Where do you put something which has indefinite length? It's not 
infinite, but you don't know how long it is. For example:

def gen():
    while random.random() < 0.5:
        yield "spam"

Obviously this isn't a collection, as such, its an iterator, but I could 
write a lazy collection which similarly has a finite but indefinite 
length that isn't known ahead of time and so can't be reversed. 
Something like a stream of data coming from an external device perhaps? 
You can't reverse it, not because it is infinite, but because you don't 
know how far forward to go to get the last item.



-- 
Steve