Complexity of splits

[Terry Reedy]

"Jean-Guillaume Pyraksos" <jeapy at free.fr> wrote in message
news:jeapy-98A462.15570212052003 at malibu.unice.fr...
> As I am digging into my Python studies, I started translating some
> elementary Lisp recursive algorithms...

The answer to your question below depends on your purpose of doing the
above.  Lets assume that its to learn more about Python in relation to
your current knowledge of Lisp, so that efficiency and feasibilily
with loooong lists is not a concern.

> a primitive operation in Python, did I miss it ? Probably. What's
the
> name of that operation  so that the recursive algorithm stays O(n) ?
I
> don't want (for now) to translate it into a loop.

Leaving aside the difference between linked vs. array implementation,
the key difference is that Lisp lists are built back to front (and
split apart front to back in reverse) while Python lists are built
front to back, and so should be split in reverse back to front.  So
'last = L.pop()' (with L becoming 'rest') is the primative you are
looking for.  Your basic strategy is to use that to replace car and
cdr and work in reverse after copying (if you want to keep the
original intact, as Alex mentioned) and reversing (with L.reverse() as
a separate statement), if necessary.

Terry J. Reedy