Questions on Using Python to Teach Data Structures and Algorithms
Brendon Towle
btowle at carnegielearning.com
Thu Sep 28 09:23:48 EDT 2006
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.
More information about the Python-list
mailing list