--- On Fri, 1/29/10, Stephen J. Turnbull <step...@xemacs.org> wrote: > > > Lisp lists are really stacks > > No, they're really (ie, concretely) singly-linked > lists. > > Now, stacks are an abstract data type, and singly-linked > lists provide > an efficient implementation of stacks. But that's not > what linked > lists "really are". For example, singly-linked lists > are also a > reasonable way to implement inverted trees (ie, the node > knows its > parent, but not its children), which is surely not a > stack.
I like your distinction between abstract data types and concrete implementations. >From a mutability perspective, the concrete implementation of Python lists >shares a performance characteristic with most concrete implementations of >stacks, in that inserts/pops at the top are cheap. Unlike most stacks, Python lists do at least semantically allow queue-like behavior for removing elements from the bottom, but I don't think it's unfair of me to say that removes from the bottom are discouraged under the current implementation. (I can cite the tutorial, for example). So, to the extent that removes from the bottom are frowned upon, Python again has the same mutability characteristics as a stack. The abstract data type "stack" does not allow for random access of elements AFAIK, so Python lists are definitely more than a stack, especially since random accesses are not only possible, they are quite efficient. So I guess they are an array. I don't know whether or not "arrays" are considered to be an abstract data type or not, but my de facto concept of an array is something that supports fast random access, cheap mutation at the top, and no guarantees at the bottom. I am guessing that from a big-O perspective, Python lists have the exact same performance characteristics as the data structures that Perl, Ruby, and Javascript all call "array." Also, Python lists are built on top of a C array, and while it would be a bit of an overstatement to say that lists are just a nicely sugared encapsulation of C arrays, I think it would be a fair statement to say that Python lists only give O(1) performance for the same operations as the underlying C array; all the other operations are there just for convenience where performance is not a driving concern. Also, we can go back to the example of LISP, the one language that I know of that shares the term "list." Whatever a "list" denotes from an abstract perspective, Python and LISP do not agree upon the definition. Python lists are more like right-side-up stacks with fast random access, while LISP lists are more like an upside-down stack without iteration. > The Python use of "list" to denote what is concretely a > dynamically > extensible one-dimensional array confused me a bit. > But what the > heck, Guido needed a four-letter word to denote a concrete > type used > to implement a mutable sequence ADT, and he wasn't going to > borrow one > from that French guy on the ramparts, right? No big > deal. Ahem... Probably the same reason he didn't call dictionaries "hashes", right? :) _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
