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

Discussion in 'Python' started by Brendon Towle, Sep 28, 2006.

1. ### Brendon TowleGuest

Some of your Lisp translations are subtly off...

> Date: 28 Sep 2006 02:49:50 -0700
> From: "sturlamolden" <>
> Subject: Re: Questions on Using Python to Teach Data Structures and
> Algorithms
> To:
>
> 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. <> +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

Brendon Towle, Sep 28, 2006

2. ### Bruno DesthuilliersGuest

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" <>
>> Subject: Re: Questions on Using Python to Teach Data Structures and
>> Algorithms
>> To:
>>
>> 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 ''.split('@')])"

Bruno Desthuilliers, Sep 28, 2006

3. ### MonkeeSageGuest

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

MonkeeSage, Sep 28, 2006
4. ### sturlamoldenGuest

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".

sturlamolden, Sep 28, 2006
5. ### Fredrik LundhGuest

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>

Fredrik Lundh, Sep 28, 2006