Re: Can't take the tail of a list without copying via List[1:]?

Guido.van.Rossum@cwi.nl
Mon, 08 Aug 1994 15:53:33 +0200

Aaron Watters:
> > Summary: Can I or why can't I take the cdr of a list without
> > copying the entire top level structure of the list?
> >
> > def NeatStuff(List):
> > Head,Tail = List[0],List[1:]
> > if Head=1:
> > GroovyStuff(Tail)
> > elif Head=2:
> > NastyStuff(Tail)
> > else:
> > NeatStuff(Tail)
> >
> > Unfortunately List[1:] makes a _copy_ of the top level structure of the
> > rest of List, which is quite expensive for large lists if all I want
> > is Common Lisp's (rest List) which gives me the rest of List without
> > copying anything.

Steve Majewski:
> You could try:
>
> def NeatStuff(List):
> Head = List[0]
> del List[0]
> Tail = List
>
> Which will remove the first element of the list ( after assigning
> to Head ). Obviously, the "Tail = List" is redundant and is there
> just to keep the names the same as in the example.

That's all fine, but you'll find life easier if you get used to a more
"Pythonic" way of doing things. In this case, Python calls for an
explicit for loop over the list. How about the following solution,
which still lets you define arbitrary functions (as long as they
handle an item at a time):

def NeatStuff(item):
if item==1: return GroovyStuff
if item==2: return NastyStuff
return NeatStuff
...similar for GroovyStuff and NastyStuff...

func = NeatStuff
for item in List:
func = func(item)

This avoids the tail recursion that both Aaron's and Steve's solution
incur; Python is not optimized for tail recursion (or any other
recursion). I haven't profiled this, but I expect that in cases where
it matters at all (i.e. when the list is long) the overhead of tail
recursion is actually much more noticeable than that of copying the
entire list (which is actually done fairly efficiently, only
incrementing the reference count of the contained elements).

Of course, I may have misunderstood Aaron's problem entirely, and he
may not require a loop over the whole list, only over the first few
elements -- in this case, I expect that the cost of copying the tail a
few times isn't actually very noticeable...

Cheers,

--Guido van Rossum, CWI, Amsterdam <Guido.van.Rossum@cwi.nl>
<URL:http://www.cwi.nl/cwi/people/Guido.van.Rossum.html>