Questions on Using Python to Teach Data Structures and Algorithms

[Brendon Towle]

On 28 Sep 2006, at 8:05 AM, python-list-request at python.org wrote:

> From: Bruno Desthuilliers <onurb at xiludom.gro>
> Subject: Re: Questions on Using Python to Teach Data Structures and
> 	Algorithms
> To: python-list at python.org
>
> Brendon Towle wrote:
>> Some of your Lisp translations are subtly off...
>
> Seems correct to me. Lisp lists are linked lists, not arrays.
>
>>
>>> Date: 28 Sep 2006 02:49:50 -0700
>>> From: "sturlamolden" <sturlamolden at yahoo.no>
>>> Subject: Re: Questions on Using Python to Teach Data Structures and
>>>     Algorithms
>>> To: python-list at python.org
>>>
>>> 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, 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.

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.


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]]]]

But, I think that's a bit silly.


>>> 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.

B.

-- 
Brendon Towle, PhD
Cognitive Scientist
+1-412-690-2442x127
Carnegie Learning, Inc.
The Cognitive Tutor Company ®
Helping over 375,000 students in 1000 school districts succeed in math.