Questions on Using Python to Teach Data Structures and Algorithms

[Bruno Desthuilliers]

Brendon Towle wrote:
> On 28 Sep 2006, at 8:05 AM, python-list-request at python.org wrote:
> 
>> From: Bruno Desthuilliers <onurb at xiludom.gro>
>>
>> Brendon Towle wrote:
>>> Some of your Lisp translations are subtly off...
>>
>> Seems correct to me. Lisp lists are linked lists, not arrays.
>>
>>>
>>>> From: "sturlamolden" <sturlamolden at yahoo.no>
>>>>
>>>> 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:

def length(linkedlist):
  return cdr(linkedlist) and  1 + length(cdr(linkedlist)) or 1

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 'onurb at xiludom.gro'.split('@')])"