[Edu-sig] Python for CS101

[Toby Donaldson]

>> For instance, to write an efficient queue data structure (where adding
>> and removing form the queue are always constant-time operations) in
>> LISP/Scheme requires using arrays.
>
>Hi Toby,
>
>I don't think this is a valid criticism.  If the point of using a queue is
>to teach how to write an efficient data structure, is the target audience
>really going to be beginners?  Do beginners care about efficiency, to the
>exclusion of all else?

If beginners don't care about the efficiency of queues, then they need to
learn otherwise. Performance is certainly not the only thing, but it was one
of the most important things, especially for an object that is going to be
re-used again and again.

>What you said is also technically wrong: there are efficent ways to
>implement queues with pure list structures.  See:
>
>    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/210459
>
>which is basically a translation of a Lisp-friendly queue class.

Indeed, this is a neat trick for implementing queues with stacks. 

However, it's not the best implementation for simple fixed capacity queues
where each add/remove operation is required to finish in constant time (as
opposed to amortized constant time). I don't know any way to achieve that in
LISP using only lists.

>The discussion in the link above also shows that it's perfectly easy ---
>and all too often likely --- for beginners to do silly things using
>Python's lists too.  On Python-tutor, we often do get beginners who will
>do things like list.pop(0), and not understand why it goes so slowly,
>compared to doing list.pop().

>Abstractions always leak.  But I wouldn't say that Python is flawed
>because it makes it easy to do list.pop(0), nor would I say Lisp is flawed
>because it makes it easy to use linked lists.

True. I would agree with this statement. The flaw in LISP is the fact that
it requires *both* the use of lists and arrays to implement certain
elementary algorithms in the best way, and that the lists and arrays have
different interfaces.

Perhaps "imperfection" is a nicer term than "flaw". :-)

Toby