Linked lists (was Re: Typing system vs. Java
Alex Martelli
aleax at aleax.it
Wed Aug 8 05:10:47 EDT 2001
"Ville Vainio" <vvainio at karhu.tp.spt.fi> wrote in message
news:yoxk80f86lf.fsf at karhu.tp.spt.fi...
> xtian at hyperactive.co.nz writes:
>
> > That's pretty spectacularly neat.
>
> Yes, it is. Gems like that should end up in the tutorial to "whet the
> appetite". Now all we need is an iterator for the list, no batter how
> tainted and impure that might be... ;-)
Maybe a generator...?
def listiter(alist):
while alist:
head, alist = alist
yield head
This will blow up if alist isn't a proper lisp-ish list, as
build with "def cons(car,cdr): return car, cdr" and a () (or
other representation of NIL that evaluates to false in Python),
and I'm not sure if such a simple case is appropriate for
a generator, but I think it would work (though I can't test
it right now -- no 2.2 installed here at work).
Or maybe to get in the LISP'ish spirit one might tail-recurse?-)
> How does this kind of list improve performance of lisp-ish recursive
> functions, as opposed to cdr = list[1:]? I guess there was a benchmark
> a while ago (some kind of "language shootout") that did use list[1:]
> and made Python look bad.
I have my doubts this will perform all that well, even if there's
something that makes allocating and freeing pairs (two-items-tuples)
*quite* fast (a 'free pool' for such object specifically, or...).
Python does no tail-recursion optimization, and well-written
"lisp-ish recursive functions" tend to depend on that to get
acceptable performance!-)
Alex
More information about the Python-list
mailing list