Python and Lisp : car and cdr

[Steven D'Aprano]

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