Strange behaviour with reversed()

Discussion in 'Python' started by Steven D'Aprano, Oct 18, 2007.

  1. I don't understand how reversed() is operating. I've read the description
    in the docs:

    reversed(seq)
    Return a reverse iterator. seq must be an object which supports the
    sequence protocol (the __len__() method and the __getitem__() method with
    integer arguments starting at 0). New in version 2.4.

    and help(reversed) but neither gives any insight to what happens when you
    use reversed() on a sequence, then modify the sequence.


    This works as I expected:

    >>> L = list("abc")
    >>> RL = reversed(L)
    >>> del L
    >>> list(RL)

    ['c', 'b', 'a']

    This suggests that reversed() makes a copy of the list:

    >>> L = list("abc")
    >>> RL = reversed(L)
    >>> L.append("d")
    >>> list(RL)

    ['c', 'b', 'a']

    This suggests that reversed() uses a reference to the original list:

    >>> RL = reversed(L)
    >>> L[0] = 'e'
    >>> list(RL)

    ['d', 'c', 'b', 'e']

    And these examples suggests that reversed() is confused, or at least
    confusing:

    >>> RL = reversed(L)
    >>> del L[2]
    >>> list(RL)

    []

    >>> L = list("abc")
    >>> RL = reversed(L)
    >>> L.insert(0, "d")
    >>> L

    ['d', 'a', 'b', 'c']
    >>> list(RL)

    ['b', 'a', 'd']


    Does anyone know what reversed() is actually doing?



    --
    Steven.
    Steven D'Aprano, Oct 18, 2007
    #1
    1. Advertising

  2. Steven D'Aprano

    Ben Finney Guest

    Steven D'Aprano <> writes:

    > and help(reversed) but neither gives any insight to what happens
    > when you use reversed() on a sequence, then modify the sequence.


    I would think the answer is the same for any question about modifying
    sequences while iterating: "undefined, therefore don't do that".

    In other words, if you think you'll be modifying the sequence during
    iteration (even if you're iterating indirectly via something like
    reversed()), iterate over a copy instead.

    --
    \ "Professionalism has no place in art, and hacking is art. |
    `\ Software Engineering might be science; but that's not what I |
    _o__) do. I'm a hacker, not an engineer." -- Jamie W. Zawinski |
    Ben Finney
    Ben Finney, Oct 18, 2007
    #2
    1. Advertising

  3. En Thu, 18 Oct 2007 01:31:13 -0300, Steven D'Aprano
    <> escribió:

    > I don't understand how reversed() is operating. I've read the description
    > in the docs:
    >
    > reversed(seq)
    > Return a reverse iterator. seq must be an object which supports the
    > sequence protocol (the __len__() method and the __getitem__() method with
    > integer arguments starting at 0). New in version 2.4.
    >
    > and help(reversed) but neither gives any insight to what happens when you
    > use reversed() on a sequence, then modify the sequence.


    A reversed object is rather simple: it stores the original sequence (a
    reference, as usual, not a copy!) and the next index to use, starting at
    len-1. Each time the next() method is called, the index is decremented
    until it goes below 0.
    This is more or less the equivalent Python code:

    class Reversed:
    def __init__(self, seq):
    n = len(seq)
    self.index = n-1
    self.seq = seq

    def __iter__(self):
    return self

    def next(self):
    index = self.index
    if index>=0:
    try: item = self.seq[index]
    except (IndexError,StopIteration): pass
    else:
    self.index -= 1
    return item
    self.index = -1
    self.seq = None
    raise StopIteration

    Note that the starting index is determined at creation time, not when the
    iteration begins. So, if you create a reversed object over a list
    containing 3 elements, the first returned element will be seq[2], then
    seq[1], then seq[0]. It doesn't matter if you modify the list after
    creating the reversed object but before starting the iteration: it will
    start at seq[2] even if it's not the last item, and will silently stop if
    seq[2] is not a valid index anymore.

    --
    Gabriel Genellina
    Gabriel Genellina, Oct 18, 2007
    #3
  4. On Oct 17, 9:31 pm, Steven D'Aprano <st...@REMOVE-THIS-
    cybersource.com.au> wrote:
    > I don't understand how reversed() is operating. I've read the description
    > in the docs:
    >
    > reversed(seq)
    > Return a reverse iterator. seq must be an object which supports the
    > sequence protocol (the __len__() method and the __getitem__() method with
    > integer arguments starting at 0). New in version 2.4.
    >
    > and help(reversed) but neither gives any insight to what happens when you
    > use reversed() on a sequence, then modify the sequence.
    >
    > This works as I expected:
    >
    > >>> L = list("abc")
    > >>> RL = reversed(L)
    > >>> del L
    > >>> list(RL)

    >
    > ['c', 'b', 'a']
    >
    > This suggests that reversed() makes a copy of the list:
    >
    > >>> L = list("abc")
    > >>> RL = reversed(L)
    > >>> L.append("d")
    > >>> list(RL)

    >
    > ['c', 'b', 'a']
    >
    > This suggests that reversed() uses a reference to the original list:
    >
    > >>> RL = reversed(L)
    > >>> L[0] = 'e'
    > >>> list(RL)

    >
    > ['d', 'c', 'b', 'e']
    >
    > And these examples suggests that reversed() is confused, or at least
    > confusing:
    >
    > >>> RL = reversed(L)
    > >>> del L[2]
    > >>> list(RL)

    >
    > []
    >
    > >>> L = list("abc")
    > >>> RL = reversed(L)
    > >>> L.insert(0, "d")
    > >>> L

    >
    > ['d', 'a', 'b', 'c']>>> list(RL)
    >
    > ['b', 'a', 'd']
    >
    > Does anyone know what reversed() is actually doing?
    >
    > --
    > Steven.


    Without knowing the internals, it seems reversed() does exactly the
    same as the following class:


    class Reversed(object):
    def __init__(self,seq):
    self.seq = seq
    self.i = len(seq)
    def __iter__(self):
    return self
    def next(self):
    self.i -= 1
    if self.i < 0:
    raise StopIteration
    else:
    return self.seq[self.i]

    so it doesn't copy anything, just book-keeping of indexes. I guess one
    would call this kind of object a (special) "view" of the sequence.

    Cheers,

    Andreas
    Andreas Kraemer, Oct 18, 2007
    #4
  5. On Thu, 18 Oct 2007 02:49:12 -0300, Gabriel Genellina wrote:

    > A reversed object is rather simple: it stores the original sequence (a
    > reference, as usual, not a copy!) and the next index to use, starting at
    > len-1. Each time the next() method is called, the index is decremented
    > until it goes below 0.


    ....

    > Note that the starting index is determined at creation time, not when
    > the iteration begins. So, if you create a reversed object over a list
    > containing 3 elements, the first returned element will be seq[2], then
    > seq[1], then seq[0]. It doesn't matter if you modify the list after
    > creating the reversed object but before starting the iteration: it will
    > start at seq[2] even if it's not the last item, and will silently stop
    > if seq[2] is not a valid index anymore.


    You know, that's probably the *least* intuitive behaviour possible.

    For reversed() to iterate over the input as it was at creation time is a
    reasonable design choice; for it to iterate over the input as it is at
    call time is also a reasonable design choice; but for it to iterate over
    some unholy mutant melding of the sequence as-it-was and as-it-is is
    simply bizarre. I hope it just fell out of the implementation and wasn't
    a deliberate design choice.


    --
    Steven.
    Steven D'Aprano, Oct 18, 2007
    #5
  6. On Thu, 18 Oct 2007 15:24:27 +1000, Ben Finney wrote:

    > Steven D'Aprano <> writes:
    >
    >> and help(reversed) but neither gives any insight to what happens when
    >> you use reversed() on a sequence, then modify the sequence.

    >
    > I would think the answer is the same for any question about modifying
    > sequences while iterating: "undefined, therefore don't do that".


    That's not correct. You can modify sequences while iterating, and the
    results are often perfectly predictable (but watch out for off-by-one
    errors):

    >>> L = range(5)
    >>> for item in L: # iterate over half of L

    .... print item, "- deleting last item =", L[-1]
    .... del L[-1]
    ....
    0 - deleting last item = 4
    1 - deleting last item = 3
    2 - deleting last item = 2


    (BTW, I'm not implying that the above is good practice. Far from it.)

    The result of modifying sequences while you iterate over them is often --
    not always -- hard to predict, but it is rarely indeterminate or
    undefined.

    enumerate(), for example, iterates over the input sequence *as it is* at
    call time, not creation time. The result of modifying the sequence is
    well defined, but not necessarily what you want. For an exercise in
    Sorcerer's Apprentice, try this:

    L = range(10)
    for i, x in enumerate(L):
    print i, x
    L.append("another!")

    Remember, ctrl-C to interrupt Python.


    But even if it is undefined in the case of reversed(), there should be
    some sort of note in the docs. By analogy with sorted(), reversed() looks
    like it should make a copy. And if not, it looks like it should iterate
    over the input sequence as it exists when called. In fact, it does a
    little of both.


    > In other words, if you think you'll be modifying the sequence during
    > iteration (even if you're iterating indirectly via something like
    > reversed()), iterate over a copy instead.


    By analogy with sorted(), reversed() looks like it should be iterating
    over a copy. In any case, it isn't clear from the docs that reversed() is
    actually a type of view. I like views, it's just that I like to know when
    I'm working with one.


    --
    Steven.
    Steven D'Aprano, Oct 18, 2007
    #6
  7. Steven D'Aprano

    Duncan Booth Guest

    Steven D'Aprano <> wrote:

    >> Note that the starting index is determined at creation time, not when
    >> the iteration begins. So, if you create a reversed object over a list
    >> containing 3 elements, the first returned element will be seq[2],

    then
    >> seq[1], then seq[0]. It doesn't matter if you modify the list after
    >> creating the reversed object but before starting the iteration: it

    will
    >> start at seq[2] even if it's not the last item, and will silently

    stop
    >> if seq[2] is not a valid index anymore.

    >
    > You know, that's probably the *least* intuitive behaviour possible.
    >
    > For reversed() to iterate over the input as it was at creation time is

    a
    > reasonable design choice; for it to iterate over the input as it is at
    > call time is also a reasonable design choice; but for it to iterate

    over
    > some unholy mutant melding of the sequence as-it-was and as-it-is is
    > simply bizarre. I hope it just fell out of the implementation and

    wasn't
    > a deliberate design choice.


    You mean that you don't find it intuitive that it iterates through the
    indices that existed at creation time and returns the values as they are
    now? I'd have said that was the *most* intuitive behaviour.

    The only other behaviours I would regard as intuitive for iteration over
    a mutating sequence would be to throw an exception either for mutating
    the sequence while the iterator exists or for using the iterator after a
    mutation.
    Duncan Booth, Oct 18, 2007
    #7
  8. On Oct 18, 2:25 am, Duncan Booth <> wrote:
    > Steven D'Aprano <> wrote:
    > >> Note that the starting index is determined at creation time, not when
    > >> the iteration begins. So, if you create a reversed object over a list
    > >> containing 3 elements, the first returned element will be seq[2],

    > then
    > >> seq[1], then seq[0]. It doesn't matter if you modify the list after
    > >> creating the reversed object but before starting the iteration: it

    > will
    > >> start at seq[2] even if it's not the last item, and will silently

    > stop
    > >> if seq[2] is not a valid index anymore.

    >
    > > You know, that's probably the *least* intuitive behaviour possible.

    >
    > > For reversed() to iterate over the input as it was at creation time is

    > a
    > > reasonable design choice; for it to iterate over the input as it is at
    > > call time is also a reasonable design choice; but for it to iterate

    > over
    > > some unholy mutant melding of the sequence as-it-was and as-it-is is
    > > simply bizarre. I hope it just fell out of the implementation and

    > wasn't
    > > a deliberate design choice.

    >
    > You mean that you don't find it intuitive that it iterates through the
    > indices that existed at creation time and returns the values as they are
    > now? I'd have said that was the *most* intuitive behaviour.
    >
    > The only other behaviours I would regard as intuitive for iteration over
    > a mutating sequence would be to throw an exception either for mutating
    > the sequence while the iterator exists or for using the iterator after a
    > mutation.


    Maybe it would have been slightly more intuitive if reversed() had
    been implemented like this,

    def Reversed(seq):
    for i in xrange(len(seq)-1,-1,-1):
    yield seq

    so that the length of the sequence is determined when the iteration
    starts, not when the iterator is created?

    The unfortunate naming may also have added to the confusion since its
    similarity to "sorted" suggests that a copy of the list is returned.
    However,

    >>> type(reversed([]))

    <type 'listreverseiterator'>

    and for comparison

    >>> type(iter([]))

    <type 'listiterator'>

    reveals what it really is.

    -Andreas
    Andreas Kraemer, Oct 18, 2007
    #8
  9. Steven D'Aprano

    Terry Reedy Guest

    "Steven D'Aprano" <> wrote in message
    news:...
    |I don't understand how reversed() is operating. I've read the description
    | in the docs:
    |
    | reversed(seq)
    | Return a reverse iterator. seq must be an object which supports the
    | sequence protocol (the __len__() method and the __getitem__() method with
    | integer arguments starting at 0). New in version 2.4.

    The input specification strongly suggests that rev.next() successively
    yields seq[len(seq)-1], ..., seq[0]

    The main question is when len(seq) is called -- on creation as it is, or
    immediately before the first yield as you appear to expect, and as it would
    be in this generator (which does NOT match the actual implementation):

    def rev(seq):
    n = len(seq)
    while n:
    n =-1
    yield seq[n]

    If len(seq) were called repeatedly (after the yield, for instance), then
    termination would no longer guaranteed (see below).

    I suppose the doc could be augmented with "The iterator is intialized once
    with len(sequence) when it is created, rather than when first used or
    anytime thereafter." But I wonder whether that would confuse those not
    thinking about corner case nuances.

    | and help(reversed) but neither gives any insight to what happens when you
    | use reversed() on a sequence, then modify the sequence.

    The sequence can potentially be modified between all calls to RL.next, and
    not just before the first as in your examples.

    abcs = list('abc')
    for a in reversed(abcs):
    print a
    abcs.append(a)

    The 'reverse' of a changing sequence, especially one changing in length, is
    a poorly defined concept.

    | >>> L = list("abc")
    | >>> RL = reversed(L)
    | >>> del L
    | >>> list(RL)
    | ['c', 'b', 'a']
    |
    | This suggests that reversed() makes a copy of the list:

    Nope. 'del L' merely removes the association between 'L' and the list,
    leaving the internal association between RL and the list and hence the list
    itself. So the above is consistent with storing a reference (and an index
    initialized to len-1).

    | >>> L = list("abc")
    | >>> RL = reversed(L)
    | >>> L.append("d")
    | >>> list(RL)
    | ['c', 'b', 'a']
    |
    | This suggests that reversed() uses a reference to the original list:

    It suggests that it uses a reference and an index initialized to len-1 when
    reversed is called (rather than when RL.next is first called).

    | >>> RL = reversed(L)
    | >>> L[0] = 'e'
    | >>> list(RL)
    | ['d', 'c', 'b', 'e']
    |
    | And these examples suggests that reversed() is confused, or at least
    | confusing:

    This is completely consist with iterating down via reference and index.

    | >>> RL = reversed(L)
    | >>> del L[2]
    | >>> list(RL)
    | []

    In the internal loop of list, RL first tries to return L[2]. But that
    raises an exception, so RL quits

    Terry Jan Reedy
    Terry Reedy, Oct 18, 2007
    #9
  10. Steven D'Aprano

    Dustan Guest

    On Oct 18, 3:52 am, Steven D'Aprano <st...@REMOVE-THIS-
    cybersource.com.au> wrote:
    > On Thu, 18 Oct 2007 15:24:27 +1000, Ben Finney wrote:
    > > Steven D'Aprano <> writes:

    >
    > >> and help(reversed) but neither gives any insight to what happens when
    > >> you use reversed() on a sequence, then modify the sequence.

    >
    > > I would think the answer is the same for any question about modifying
    > > sequences while iterating: "undefined, therefore don't do that".

    >
    > That's not correct. You can modify sequences while iterating, and the
    > results are often perfectly predictable (but watch out for off-by-one
    > errors):


    Perhaps a better word to use here would have been "undocumented", and
    therefore unsafe to use, as it might differ in different versions, or
    in different data-types. Dictionaries cannot continue iteration once
    they have changed size.
    Dustan, Oct 18, 2007
    #10
  11. Steven D'Aprano

    Duncan Booth Guest

    Andreas Kraemer <> wrote:

    >> The only other behaviours I would regard as intuitive for iteration over
    >> a mutating sequence would be to throw an exception either for mutating
    >> the sequence while the iterator exists or for using the iterator after a
    >> mutation.

    >
    > Maybe it would have been slightly more intuitive if reversed() had
    > been implemented like this,
    >
    > def Reversed(seq):
    > for i in xrange(len(seq)-1,-1,-1):
    > yield seq
    >
    > so that the length of the sequence is determined when the iteration
    > starts, not when the iterator is created?


    Perhaps, but either way it comes down to "don't modify the sequence while
    iterating".
    Duncan Booth, Oct 19, 2007
    #11
  12. On Oct 19, 1:49 pm, Duncan Booth <> wrote:
    > Andreas Kraemer <> wrote:
    > >> The only other behaviours I would regard as intuitive for iteration over
    > >> a mutating sequence would be to throw an exception either for mutating
    > >> the sequence while the iterator exists or for using the iterator after a
    > >> mutation.

    >
    > > Maybe it would have been slightly more intuitive if reversed() had
    > > been implemented like this,

    >
    > > def Reversed(seq):
    > > for i in xrange(len(seq)-1,-1,-1):
    > > yield seq

    >
    > > so that the length of the sequence is determined when the iteration
    > > starts, not when the iterator is created?

    >
    > Perhaps, but either way it comes down to "don't modify the sequence while
    > iterating".


    Definitely agreed.
    Andreas Kraemer, Oct 19, 2007
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David Li

    the byte be reversed! why?

    David Li, Apr 24, 2005, in forum: C++
    Replies:
    7
    Views:
    431
    David Li
    Apr 24, 2005
  2. mark
    Replies:
    2
    Views:
    271
    Dave K
    Jan 3, 2004
  3. Stefan Behnel

    reversed heapification?

    Stefan Behnel, Mar 7, 2005, in forum: Python
    Replies:
    6
    Views:
    305
    Stefan Behnel
    Mar 7, 2005
  4. Replies:
    13
    Views:
    417
    Sion Arrowsmith
    Nov 6, 2006
  5. bit reversed order

    , Aug 17, 2007, in forum: VHDL
    Replies:
    1
    Views:
    1,473
Loading...

Share This Page