Toby Donaldson wrote: > On 5/6/05 8:47 PM, "John Zelle" <[EMAIL PROTECTED]> wrote: >
>>For the record, it's very easy in LISP to implement a Queue using a >>cons-pair with car pointing to the front of a linked list and cdr >>pointing to the back. Using such a structure, constant time enqueue and >>dequeue is trivial without arrays or amortized analysis. LISP allows one >>to easily build any linked structure you'd like. There is no restriction >>to a linear list with only a head (car) pointer. >> >>Of course implementing something like a queue which has state >>(side-effects) is not pure functional programming, but real LISP >>programmers don't worry too much about that. > > > Thanks for pointing this out; I did a bit of searching on the web and found > an implementation of what you are referring to. I'd never seen this before. > I guess I should know better than to doubt what's possible in Common LISP. > :-) Here's the code: > > (defun enqueue (obj queue) > "Enqueue an object. Return the queue." > (if (cdr queue) > (setf (cdr (cdr queue)) (list obj) > (cdr queue) (cdr (cdr queue))) > (setf (cdr queue) (list obj) > (car queue) (cdr queue))) > queue) > > > (defun dequeue (queue) > "Dequeue an object. Return the object queued." > (when (cdr queue) > (prog1 > (caar queue) > (if (eq (cdr queue) > (car queue)) > (setf (car queue) nil > (cdr queue) nil)) > (setf (car queue) (cdr (car queue)))))) > > Again, I think it is still an example of a design flaw in LISP because it > violates the precept "simple things should be done simply". > This _is_ a simple implementation of an indefinitely long queue. A linked list with head and tail pointers is the classic way of solving this problem. You seem to have some bias against linked structures. They are not inherently more complicated than arrays, just different. > <snipped here> > > One could argue that in, say, C, the simple way to implement a fixed-sized > queue is as a circular array. If you believe that, then I would suggest that > is an example of good design: the simple solution to a simple problem is > also the most efficient. > > Ah, the key here is that you are restricting yourself to a fixed size queue. Arguably a circular array is the best solution. However, it is not necessarily a trivial implementation. As anyone who has actually implemented this will tell you, one has to be very careful about how full and empty conditions are handled. It's not hard, but it is subtle. I've seen many flawed queue implementations. > If one uses linked lists, then it is a flaw in Python. Personally, I have > never needed a linked list in Python. > I can't agree with this statement. There are many situations where a linked structure us the _right_ implementation of a particular abstraction. If you want an indefinitely large queue in Python with constant time operations, then a linked list is probably the best way to do it. Furthermore, it is very easy to implement this in Python. Using linked lists for this in no way illustrates any flaw in Python. The reason you may not have seen linked lists in Python is that the built-in continguous implementation is so good. Still, there are cases where reference-based linked structures are a good thing: ordered structures with constant time insertion, graphs, trees, sparse matricies (perhaps), etc. Sometimes, the linked list is entirely hidden in the logic of the problem. I once did a backtracking solution to n queens in Python and discovered only after the fact that I had actually built a linked list. > >>If your argument is that both kinds of structures should have exactly >>the same interface, that adds to the beginner's confusiuon over >>efficiency that you argued above. By only providing the operations that >>are efficient for the particular structure, LISP helps the novice >>programmer use the more appropriate structure for a given task. > > > Interesting argument. Although in Common LISP the "nth" function retrieves > list items in linear time, so inefficient list operations are provided. > True enough. I was only saying that your arguments seemed to be inconsistent. Not claiming that Common Lisp had necessarily taken this approach. > Do you think Python would be a better language for beginners if a fixed-size > array data type was added to it that had a different interface than the > current dynamic lists? > No. The operations that are efficient on a fixed size array are the same operations that are efficient on Python lists. For example, your fixed-sized (circular) queue can easily be implemented using a Python list. I think we agree that the "right" thing in this case is that programmers should be aware of what the Python list does and, when necessary, be able to optimize their code to use efficient operations. The important thing to keep in mind is that it is not a design flaw simply that a language makes it easy to write inefficient programs. This is ususally the sign of a higher-level language. It becomes easier to write an inefficient program simply because it is easier to write programs period. Again, the queue example shows this. It is absolutely trivial to implement using append and pop(0). If O(n) efficiency is good enough for the problem at hand, what's wrong with that? --John -- John M. Zelle, Ph.D. Wartburg College Professor of Computer Science Waverly, IA [EMAIL PROTECTED] (319) 352-8360 _______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
