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] def length(L): if not L: return 0 return 1 + length(cdr(L)) L = (a, (b, (c, (d, None)))) length(L) is O(n) -- http://mail.python.org/mailman/listinfo/python-list