Re: Questions on Using Python to Teach Data Structures and Algorithms
- From: Bruno Desthuilliers <onurb@xxxxxxxxxxx>
- Date: Thu, 28 Sep 2006 17:24:54 +0200
Brendon Towle wrote:
On 28 Sep 2006, at 8:05 AM, python-list-request@xxxxxxxxxx wrote:
From: Bruno Desthuilliers <onurb@xxxxxxxxxxx>
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@xxxxxxxx>
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@xxxxxxxxxxx'.split('@')])"
.
- References:
- Re: Questions on Using Python to Teach Data Structures and Algorithms
- From: Brendon Towle
- Re: Questions on Using Python to Teach Data Structures and Algorithms
- Prev by Date: Re: Questions on Using Python to Teach Data Structures and Algorithms
- Next by Date: Re: for: else: - any practical uses for the else clause?
- Previous by thread: Re: Questions on Using Python to Teach Data Structures and Algorithms
- Next by thread: Re: Questions on Using Python to Teach Data Structures and Algorithms
- Index(es):
Relevant Pages
|
