On Sun, 19 Jun 2011 05:56:27 -0700, Ethan Furman wrote: > Lie Ryan wrote: >> On 06/18/11 00:45, Franck Ditter wrote: >>> Hi, I'm just wondering about the complexity of some Python operations >>> to mimic Lisp car and cdr in Python... >>> >>> def length(L) : >>> if not L : return 0 >>> return 1 + length(L[1:]) >>> >>> Should I think of the slice L[1:] as (cdr L) ? I mean, is the slice a >>> copy of a segment of L, or do I actually get a pointer to something >>> inside L ? Is the above function length O(n) or probably O(n^2) ? >>> Where are such implementation things (well) said ? >>> >>> Thanks, >>> >>> franck >> >> Your function does not mimic Lisp's car/cdr. This one does: >> >> >> def car(L): >> return L[0] >> def cdr(L): >> return L[1] > > IANAL (I am not a Lisper), but shouldn't that be 'return L[1:]' ?
No. Each cell in a Lisp-style linked list has exactly two elements, and in Python are usually implemented as nested tuples: (head, tail) # Annoyingly, this is also known as (car, cdr). where head is the data value and tail is either another Lisp-style list or a marker for empty (such as the empty tuple () or None). So a one-element linked list might be given as: (42, None) A two element list: (42, (43, None)) Three element list: (42, (43, (44, None))) and so forth. So while you could harmlessly use a slice L[1:], there is no point, since L[1:] will have at most a single element. >> def length(L): >> if not L: return 0 >> return 1 + length(cdr(L)) > > How is this different from regular ol' 'len' ? The point is to duplicate Lisp's implementation, not to be useful :) Regular len will return 2, no matter how many elements you have in the linked list, because it doesn't look at the tail recursively. -- Steven -- http://mail.python.org/mailman/listinfo/python-list