Questions on Using Python to Teach Data Structures and Algorithms

[sturlamolden]

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]