Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #78089

Re: Is there a canonical way to check whether an iterable is ordered?

Show all headers | View raw

On 9/18/2014 10:45 PM, Chris Angelico wrote:
> On Fri, Sep 19, 2014 at 9:52 AM, Roy Smith <roy@panix.com> wrote:
>> In article <mailman.14103.1411047208.18130.python-list@python.org>,
>>   Chris Angelico <rosuav@gmail.com> wrote:
>>
>>> The one thing you can rely on (and therefore must comply with, when
>>> you design an iterable) is that iteration will hit every element

in what, a collection that exists separately from the iteration?  or a 
collection generated by the iteration?

This is actually two statements in one -- what the user can rely on, 
which I claim is very little (see below) -- and what the designer must 
'comply with', which is correspondingly very little (again see below) 
except as the designer claims otherwise in specific documentation.

>>> exactly once.

There are only two things to rely on without further, special case, 
information.

iter(iterable) = iterator (if not, 'iterable' is not an iterable)

next(iterator) = object or raises StopIteration (with raising not 
guaranteed)

The conceptual flaw in the statement above, as I think originally 
intended, is the notion that 'every element [of a collection]' exists, 
or is defined before the iteration.  Iterators can be creative, in the 
sense of generating collections as they go, in a manner not determined 
by the past.  It is also possible that the next item depends on what the 
iterator user has done with previous items.  Such feedback loops are 
common for programs that interact with users.

If the statement above is interpreted retrospectively, as "iteration 
hits every item of the sequence it generates", then it is trivially true 
and is equivalent to "iteration yields every element that it yields, in 
the order that it yields them".  To paraphase the OP's question, given 
completion of

yielded1 = [item for item in iterable]
yielded2 = [item for item in yielded1]

then yielded2 == yielded1 *is* guarenteed.  But this is all that is 
guaranteed.

Itertools.tee operates similarly to the above code except that 
processing of the duplicate streams can be interleaved.  There is an 
internal queue of items yielded on one branch not the other.  For best 
operation, accesses should be interleaved, with the maximum lag bounded. 
  Itertools.tee guarantees that the two branches yield the same items in 
the same order.

>> Does it actually say that somewhere?  For example:
>>
>> for i in bag.pick_randomly_with_replacement(n=5):
>>     print i
>>
>> shouldn't do that.
>
> When you pick randomly from a population, you create a new population,
> which may have duplicates compared to the original. (For efficiency's
> sake it probably won't all actually exist immediately, but
> conceptually it does exist.)

When the next item depends on feedback from the user, that conceptual 
trick does not work as well.

 > That's what you're iterating over - not the bag itself.

If one iterates over anything other that a sequence, in forward order, 
then one is, in effect, iterating over a new sequence generated from the 
'base' collection.  In particular, set and dict iteration iterates over 
an arbitrary serialization of the set or dict.

In the example above, the underlying collection (or specification 
thereof) and size of selection can be hidden away in a class instance so 
that the code may just look like 'for i in my_iterable:", just as for 
iterating over a set.

-- 
Terry Jan Reedy

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Is there a canonical way to check whether an iterable is ordered? cool-RR <ram.rachum@gmail.com> - 2014-09-18 04:55 -0700
  Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-18 22:10 +1000
    Re: Is there a canonical way to check whether an iterable is ordered? Roy Smith <roy@panix.com> - 2014-09-18 08:58 -0400
      Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-18 23:33 +1000
        Re: Is there a canonical way to check whether an iterable is ordered? Roy Smith <roy@panix.com> - 2014-09-18 19:52 -0400
          Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 12:45 +1000
          Re: Is there a canonical way to check whether an iterable is ordered? Terry Reedy <tjreedy@udel.edu> - 2014-09-19 18:02 -0400
          Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-20 15:01 +1000
      Re: Is there a canonical way to check whether an iterable is ordered? Terry Reedy <tjreedy@udel.edu> - 2014-09-18 09:46 -0400
      Re: Is there a canonical way to check whether an iterable is ordered? Tim Chase <python.list@tim.thechases.com> - 2014-09-18 09:32 -0500
      Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 15:15 +1000
        Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 15:40 +1000
          Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 20:59 +1000
            Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 21:19 +1000
              Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 21:58 +1000
                Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 22:06 +1000
            Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 21:25 +1000
              Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 21:46 +1000
                Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 21:56 +1000
                Re: Is there a canonical way to check whether an iterable is ordered? alister <alister.nospam.ware@ntlworld.com> - 2014-09-19 12:26 +0000
                Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 22:36 +1000
  Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 15:04 +1000

csiph-web