Well, yes: you can use data structures that perform like Lisp lists,
but not Python 'lists'. Lists in Python are really more like variable
sized arrays, than 'lists' in the Lisp/Prolog/etc. genre. They don't
do well for Lisp-like recursive processing.
But it's actually easy to represent Lisp-like 'lists' using Python's
native data structures: just use Python tuples, rather than lists.
A Python tuple of the form:
(car, cdr)
behaves exactly like a Lisp cons-cell (and Prolog '[Head|Tail]' list
constructers). This is just a binary-tree representation for linear
lists. To take the 'tail' of such a list, just use tuple assignment:
(head, tail) = List // fetch the car/cdr
or
(head, List) = List // pop and discard the car
If you build your list using these components, you can traverse them in
recursion without copying the list tail each time-- when you access the
tail/cdr, you just fetch the second item in the tuple, which is just
another tuple object (a 2-cell block), instead of copying the remainder
of the list.
In fact, tuples in Python are more convenient that 'cons' in Lisp--
they are created implicitly just by writing them (there's no explicit
'cons' call, much like [X|Y] list notation in Prolog).
For example:
L = None
for x in [1,2,3]: # a right-heavy tree
L = (x, L) # L = (cons x L)
while L: # L = (3, (2, (1,None) ))
(head, L) = L # head = (car L), L = (cdr L)
print head # 3 2 1
def travel(L): # recursive traversal
if L:
print L[0] # do something with head
travel(L[1]) # recurse on tail without copying the list
Or equivalently:
L = None
for x in [1, 2, 3]:
L = (L, x) # a left-heavy tuple tree
while L: # L = (( (None, 1), 2), 3)
(L, tail) = L
print tail
def travel(L): # recursive traversal
if L:
print L[1] # do something with head
travel(L[0]) # recurse on tail without copying while list
You could implement this all as a Python class, but it's alot faster
to just use tuples for lists in-line. BTW, I've used the tree-list
representation successfully in an expert-system shell; performance was
measurably better than native python lists, especially for large stacks
passed around recursively.
Mark Lutz
ps-- I've posted this idea before; sounds like a FAQ topic (?)