Velocity Reviews > Re: Questions on Using Python to Teach Data Structures and Algorithms

# Re: Questions on Using Python to Teach Data Structures and Algorithms

Brendon Towle
Guest
Posts: n/a

 09-28-2006
On 28 Sep 2006, at 8:05 AM, http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> From: Bruno Desthuilliers <(E-Mail Removed)>
> Subject: Re: Questions on Using Python to Teach Data Structures and
> Algorithms
> To: (E-Mail Removed)
>
> 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" <(E-Mail Removed)>
>>> Subject: Re: Questions on Using Python to Teach Data Structures and
>>> Algorithms
>>> To: (E-Mail Removed)
>>>
>>> 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.

Bruno Desthuilliers
Guest
Posts: n/a

 09-28-2006
Brendon Towle wrote:
> On 28 Sep 2006, at 8:05 AM, (E-Mail Removed) wrote:
>
>> From: Bruno Desthuilliers <(E-Mail Removed)>
>>
>> Brendon Towle wrote:
>>> Some of your Lisp translations are subtly off...

>>
>> Seems correct to me. Lisp lists are linked lists, not arrays.
>>
>>>
>>>> From: "sturlamolden" <(E-Mail Removed)>
>>>>
>>>> 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,

returns a "single level" *Lisp* list - ie, a linked 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.

It returns a structure made of a reference to the new item and a
reference to the original list. Which is exactly what Lisp's cons does
AFAIK.

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

Not if you're writing the appropriate length function:

You obviously can't use the Python builtin len() here.

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

Should actually be
[1, [2, [3, [4, []]]]]

The internal representation of a Lisp list is really (1 (2 (3 (4 ())))),
not (1 2 3 4).

If it's the fact the proposed translation uses Python lists internally
that bother you, you could also implement it with a more heavyweight
solution:

class cons(object):
def __init__(self, car, cdr=None):
self.car = car
self.cdr = cdr
def __repr__(self):
return "<cons %s %s>" % (self.car, self.cdr)

def llist(*args):
alist = None
for item in reversed(args):
alist = cons(item, alist)
print alist
return alist

def cdr(acons):
return acons.cdr

def car(acons):
return acons.car

def length(llist):
if cdr(llist) is None:
return 1
return 1 + length(cdr(llist))

> But, I think that's a bit silly.

It's *of course* a bit silly[1] - Python is not Lisp. But it's a clear
illustration of the difference between Python lists and Lisp lists !-)

[1] OTHO, using this with tuples may be (or may have been) a more
efficient implementation for stacks than plain Python lists, cf Mark
Lutz, "Programming Python", 2nd edition.

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

The original definition of cons() was by no mean "incorrect".

--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in '(E-Mail Removed)'.split('@')])"

sturlamolden
Guest
Posts: n/a

 09-28-2006

Brendon Towle wrote:

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

That is equivalent, as <list> is the remainder of the list. By list I
mean the resulting chained data structure, not the Python list as it is
an array.

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

That is indeed a discrepancy.

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

It is not at all silly. Let us look at how these lists are stored in
memory. (Use a fixed size font like courier.) First the Lisp list (1 2
3 4):

(car,cdr)
| |
1 (car,cdr)
| |
2 (car,cdr)
| |
3 (car,cdr)
| |
4 nil

Here, car is a reference to the number, cdr is a reference to the
remainder of the list.

Now look at the Python "list" [1, [2, [3, [4,null]]]]. Again, car is a
reference to the value, cons is a reference to the remainder of the
list.

[car,cdr]
| |
1 [car,cdr]
| |
2 [car,cdr]
| |
3 [car,cdr]
| |
4 null

You can see that they are indeed equivalent. In Lisp you have a pair of
references, lets call them car and cdr, one pointing to the value the
other to the remainder of the list. In Python you have the exactly same
thing.

structures and algorithms. Chaining together elements in e.g. a linked
list or a binary tree is elementary concepts. This shows how it can be
done in Python without having to define "classes" for the data
stuctures as one would in Java or (Heaven forbid) C++.

Thus I stand by my original claim. Essentlially:

def cons(car,cdr): return (car,cdr) # or [car,cdr]
def car(cons): return cons[0]
def cdr(cons): return cons[1]

MonkeeSage
Guest
Posts: n/a

 09-29-2006
sturlamolden wrote:
> Thus I stand by my original claim. Essentlially:
>
> def cons(car,cdr): return (car,cdr) # or [car,cdr]
> def car(cons): return cons[0]
> def cdr(cons): return cons[1]

I guess you were talking about implementing the _structure_ of lisp
lists in python syntax (as you seem to imply), not trying to emulate
their _behavior_ with one-dimensional python lists. That makes sense,
and your code is correct in that case; but in the other case Brendon's
code is correct. So everyone was right (only, about different things).

Regards,
Jordan

Dennis Lee Bieber
Guest
Posts: n/a

 09-29-2006
On 28 Sep 2006 21:17:38 -0700, "MonkeeSage" <(E-Mail Removed)>
declaimed the following in comp.lang.python:

(Coming in from the cold)
>
> I guess you were talking about implementing the _structure_ of lisp
> lists in python syntax (as you seem to imply), not trying to emulate

Well.... The subject line does refer "data structures" <G>

Though if this suddenly inspires the creation of a Common LISP
interpreter written in Python, I may want to close my eyes <G>
--
Wulfraed Dennis Lee Bieber KD6MOG
(E-Mail Removed) (E-Mail Removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (E-Mail Removed))
HTTP://www.bestiaria.com/

MonkeeSage
Guest
Posts: n/a

 09-29-2006
Dennis Lee Bieber wrote:
> Though if this suddenly inspires the creation of a Common LISP
> interpreter written in Python, I may want to close my eyes <G>

Hehe! I actually thought of trying that once, but I realized that I'm
too stupid and / or lazy to pull it off.

Regards,
Jordan

Dennis Lee Bieber
Guest
Posts: n/a

 09-29-2006
On 28 Sep 2006 23:07:06 -0700, "MonkeeSage" <(E-Mail Removed)>
declaimed the following in comp.lang.python:

> Hehe! I actually thought of trying that once, but I realized that I'm
> too stupid and / or lazy to pull it off.
>

My exposure to the language is an old (Pre-"Common") implementation
of Supersoft LISP on cassette tape, that ran on a TRS-80 Model III.

Oh, and that ancient text book describing the details of the
language.
--
Wulfraed Dennis Lee Bieber KD6MOG
(E-Mail Removed) (E-Mail Removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (E-Mail Removed))
HTTP://www.bestiaria.com/

Bruno Desthuilliers
Guest
Posts: n/a

 09-29-2006
Dennis Lee Bieber wrote:
> On 28 Sep 2006 21:17:38 -0700, "MonkeeSage" <(E-Mail Removed)>
> declaimed the following in comp.lang.python:
>
> (Coming in from the cold)
>> I guess you were talking about implementing the _structure_ of lisp
>> lists in python syntax (as you seem to imply), not trying to emulate

>
> Well.... The subject line does refer "data structures" <G>

Noticed that too ?-)

> Though if this suddenly inspires the creation of a Common LISP
> interpreter written in Python, I may want to close my eyes <G>

Well... Not quite Common Lisp yet, but :
http://www.biostat.wisc.edu/~annis/creations/PyLisp/

--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in '(E-Mail Removed)'.split('@')])"

sturlamolden
Guest
Posts: n/a

 09-29-2006
MonkeeSage wrote:

> > def cons(car,cdr): return (car,cdr) # or [car,cdr]
> > def car(cons): return cons[0]
> > def cdr(cons): return cons[1]

>
> I guess you were talking about implementing the _structure_ of lisp
> lists in python syntax (as you seem to imply), not trying to emulate
> their _behavior_ with one-dimensional python lists.

structures and algorithms, and the implementation details of Python
lists in particular. It may not be obvious that they are essentially
arrays under the hood.

The Lisp discussion became a digression; I was not trying to implement
Lisp in Python, but rather demonstrate the difference between Lisp
lists and Python lists.