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
Some of your Lisp translations are subtly off...

> 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: http://www.velocityreviews.com/forums/(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)

> def car(structure)
> return structure[0]
>
> def cdr(structure)
> return structure[1]

should be:
return structure[1:]

B.

--
Brendon Towle, Ph.D. <(E-Mail Removed)> +1-412-362-1530
“Debugging is twice as hard as writing the code in the first place.
Therefore,
if you write the code as cleverly as possible, you are, by
definition, not
smart enough to debug it.” – Brian W. Kernighan

Bruno Desthuilliers
Guest
Posts: n/a

 09-28-2006
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.

>> def car(structure)
>> return structure[0]
>>
>> def cdr(structure)
>> return structure[1]

>
> should be:
> return structure[1:]

idem.

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

MonkeeSage
Guest
Posts: n/a

 09-28-2006
Bruno Desthuilliers wrote:
> Brendon Towle wrote:
> > Some of your Lisp translations are subtly off...

>
> Seems correct to me. Lisp lists are linked lists, not arrays.

Actually, Brendon was correct. In lisp / scheme:

(cons 1 '(2 3)) -> (1 2 3)
(car '(1 2 3)) -> 1
(cdr '(1 2 3)) -> (2 3)

But Brendon's code also needs a correction: [a].extend(b) is wrong,
because extend is in-place and returns None, and [a] is anonymous...it
needs to be something like:

def cons(a, b):
b.insert(0, a)
return b

Regards,
Jordan

sturlamolden
Guest
Posts: n/a

 09-28-2006

Brendon Towle wrote:

> > def cons(a,b)
> > return [a,b]

>
> should be:
> return [a].extend(b)

I seem to remember that a cons joins two items, it doesn't grow a
strait list. A lisp list is a special case of a binary tree. How would
you build a tree structure with your cons? I think you are wrong here.

> > def car(structure)
> > return structure[0]
> >
> > def cdr(structure)
> > return structure[1]

>
> should be:
> return structure[1:]

With your cons yes. With mine no, as there is only two elements in each
array aka "cons cell".

Fredrik Lundh
Guest
Posts: n/a

 09-28-2006
sturlamolden wrote:

> I seem to remember that a cons joins two items, it doesn't grow a
> strait list.

http://www.lisp.org/HyperSpec/Body/fun_cons.html

"If object-2 is a list, cons can be thought of as producing a new list
which is like it but has object-1 prepended."

</F>