Brendon Towle wrote: > On 28 Sep 2006, at 8:05 AM, [EMAIL PROTECTED] wrote: > >> From: Bruno Desthuilliers <[EMAIL PROTECTED]> >> >> Brendon Towle wrote: >>> Some of your Lisp translations are subtly off... >> >> Seems correct to me. Lisp lists are linked lists, not arrays. >> >>> >>>> From: "sturlamolden" <[EMAIL PROTECTED]> >>>> >>>> If you want to make a chained structure, then perhaps you know LISP? >>>> This is what the basic machinery of LISP looks like in Python: >>>> >>>> def cons(a,b) >>>> return [a,b] >>> >>> should be: >>> return [a].extend(b) >> >> A Lisp cons is made of a reference to it's content and a reference to >> the rest of the list, so cons = lambda a, b : [a, b] seems the most >> straightforward translation. > > Yes, a lisp cons is a pair of references as you describe. However, the > following lisp call: > > ? (cons <item> <list>) > > returns a single level list,
returns a "single level" *Lisp* list - ie, a linked list. > with <item> as its new first item, and the > original contents of <list> as the remainder of the list. The OP's code > doesn't do that; it returns a list of two items, with <list> as the > second item. It returns a structure made of a reference to the new item and a reference to the original list. Which is exactly what Lisp's cons does AFAIK. > To put it another way, the following code is always true in Lisp: > > ? (= (length (cons <item> <list>)) (1+ (length <list>))) > > But the OP's code only allows that to be true when <list> is of length 1. Not if you're writing the appropriate length function: def length(linkedlist): return cdr(linkedlist) and 1 + length(cdr(linkedlist)) or 1 You obviously can't use the Python builtin len() here. > > I suppose, of course, that you could claim that the following Lisp list: > > (1 2 3 4) > > should translate into the following Python list: > > [1, [2, [3, [4]]]] Should actually be [1, [2, [3, [4, []]]]] The internal representation of a Lisp list is really (1 (2 (3 (4 ())))), not (1 2 3 4). If it's the fact the proposed translation uses Python lists internally that bother you, you could also implement it with a more heavyweight solution: class cons(object): def __init__(self, car, cdr=None): self.car = car self.cdr = cdr def __repr__(self): return "<cons %s %s>" % (self.car, self.cdr) def llist(*args): alist = None for item in reversed(args): alist = cons(item, alist) print alist return alist def cdr(acons): return acons.cdr def car(acons): return acons.car def length(llist): if cdr(llist) is None: return 1 return 1 + length(cdr(llist)) > But, I think that's a bit silly. It's *of course* a bit silly[1] - Python is not Lisp. But it's a clear illustration of the difference between Python lists and Lisp lists !-) [1] OTHO, using this with tuples may be (or may have been) a more efficient implementation for stacks than plain Python lists, cf Mark Lutz, "Programming Python", 2nd edition. > >>>> def car(structure) >>>> return structure[0] >>>> >>>> def cdr(structure) >>>> return structure[1] >>> >>> should be: >>> return structure[1:] >> >> idem. > > I should have pointed out, of course, that the original definition of > CDR was correct given the original (incorrect) definition of cons. The original definition of cons() was by no mean "incorrect". -- bruno desthuilliers python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for p in '[EMAIL PROTECTED]'.split('@')])" -- http://mail.python.org/mailman/listinfo/python-list