Complexity of splits

[Alex Martelli]

Aahz wrote:
   ...
> for example.  (I believe Lisp has "array" for that.)  If you want to
> implement the precise equivalent of the Lisp algorithm in Python, you
> need to create a Python class that implements a linked list.

You CAN create a class for that, but you may also, alternatively,
choose to use the Python built-in types 'list' or 'tuple' and a few
auxiliary functions:

def cons(a,b):
    return [a,b]

def car(cell):
    return cell[0]

def cdr(cell):
    return cell[1]

def setcar(cell, x):
    cell[0] = x

and so on.  If you don't need setcar and setcdr, you may use tuples
instead of lists (just remove the brackets in the body of cons).  Of
course, you might also want handier ways to translate from these
lispish cons-cell based lists to/from Python lists, e.g. (warning,
untested code):

def list2cons(L):
    if not L: return None
    return cons(L[0], list2cons(L[1:]))

def cons2list(cell):
    if cell is None: return []
    return [car(cell)] + cons2list(cdr(cell))

Of course, making a class would be way more Pythonic - but then,
so would it be way more Pythonic to use loops instead of recursion,
use existing built-ins rather than reimplementing them inefficiently,
and so on, and the OP seems dead set against such Pythonic choices;-).


Alex