Immutable list reverse function

[Martin Sjögren]

On Thu, Jul 19, 2001 at 04:28:51PM +0000, Terry Reedy wrote:
> 
> "Martin Sjögren" <martin at strakt.com> wrote in message
> news:mailman.995543208.24170.python-list at python.org...
> >Is there a "good" way to write a fast reverse function for immutable
> lists?
> 
> Lists are mutable.  That is why you can reverse them in place.  Three
> possible questions:

Yeah I meant immutable sequences. Or rather, an immutable reverse
function? That is, not changing the parameter.

[snip Q1]

> and similarly for str_reverse.  In 2.2a I believe we could write a more
> generic
> 
> def seq_reverse(seq):
>   t = type(seq)
>   ...
>   return t(ans)

Yea that'd be nice, but I want it to work with py1.5 :-)

> Lutz *Programming Python* p492 gives (with slight renaming) this generic
> version which will even work for sequence-like classes:
> 
> def reverse(seq):
>   ans = seq[:0]   # empty seq of same type
>   for i in range(len(seq)):
>     ans = seq[i:i+1] + ans
>   return ans

That could work, but it looks pretty slow creating new sequences all the
time. Still, if the sequence is immutable that's the way it has to be
done.

> Q2. How reverse a list and get return value to chain in call sequence?

This is not what I wanted to do from a puristic view, but seeing as the
sequencce I want to reverse often is a 'range(N)' list that'd work.

> >What I want to do is basically this: foo(reverse(create_a_list()))
> 
> If reverse returns a copy rather than the original, then the original list
> is uselessly tossed away.  So see the Q2 answer.
> 
> >Instead of having to:
> 
> >>> list = create_a_list()
> >>> list.reverse()
> >>> foo(list)
> 
> Since this does not create two lists, it is more effecient than your
> original alternative.

You know, I never thought of that, *sigh*, I think I'll stick to this, or
maybe write a small revret() function that reverses and returns.

I miss Haskell :/

Martin

-- 
Martin Sjögren
  martin at strakt.com              ICQ : 41245059
  Phone: +46 (0)31 405242        Cell: +46 (0)739 169191
  GPG key: http://www.strakt.com/~martin/gpg.html