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