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


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.

The original poster was asking about using Python for teaching data
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]

.

Relevant Pages

  • Re: simultaneous assignment
    ... that are either true or false, and the puzzle lists a few statements ... Python always represents the value "True" with a reference to a True ... To convert a random value into a boolean value, ...
    (comp.lang.python)
  • Re: Is everything a refrence or isnt it?
    ... What's stored in a list is a reference. ... Python doesn't have ... If lists held references, you could do this: ... when you're passing immutable objects. ...
    (comp.lang.python)
  • Re: why cannot assign to function call
    ... No, you give a reference to the list to a function, and the ... how CPython works under the hood with Python level code. ... sharing, maybe -- like keeping lists of clones, and magically updating ... Tcl uses pointers to values in its implementation. ...
    (comp.lang.python)
  • Re: Python Documentation (should be better?)
    ... shouldn't be there to teach like the tutorial, but for reference. ... briefly describes arrays in PHP and then lists all the functions that have ... Contrast that with Python. ... > Consider non-official manuals such as: ...
    (comp.lang.python)
  • Re: Creating a List of Empty Lists
    ... You don't need to divine the rules for copy vs. reference: Python NEVER ... A Python "pointer" is a sort of indexed name, ... lists. ...
    (comp.lang.python)