Python “lists” are not lists. A history | Hacker News Reader

Python “lists” are not lists. A history

metarabbit.wordpress.com

10 pointsdaGrevis12 comments

this is useless. In the python interface they are obviously lists. Is the author arguing that cpython implements them as C arrays? I don't know because the terms weren't defined.

If the author believes clarity will arise from pedantry, maybe he should start with wikipedia

> In computer science, a list or sequence is an abstract data type that implements a finite ordered collection of values, where the same value may occur more than once.

https://en.wikipedia.org/wiki/List_(abstract_data_type)

I was about to post something very similiar.

There's nothing uniquely strange about Python's list type being backed by an array: that is even given its own type in Java (ArrayList: http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList... which implements List<> so it "is" a list).

I think the perhaps weirdest thing about Python's list API is that it supports indexing, which is rarely done on linked lists due to the cost involved. In Python I got the feeling that it's known/expected that indexing is fast.

Well, he seems to be complaining about exactly that, "Python lists aren't lists because they're implemented internally as arrays". I agree that this article is pointless.

A list is called a list in python for the same reason the term dictionary is used -- these are the high level concepts for abstract types. The specific implementation details aren't too important, as often times you just want "the fastest in general" which python does fairly well given the constraints.

As an example, a dictionary is implemented by a hash map, but after investigation, CPython may very well decide that any dictionary smaller than N is implemented as a constant table lookup. It wouldn't be renamed to TableLookupToHashMap. That would be silly.

> a list is a list [...] these are well defined computer science terms

"list" is a CS term? I know that "(doubly|singly) linked list" is a CS term, but have never heard anyone mention list by itself (unless context made it obvious that they mean "linked list" - but then I've also seen people use the word "list" when the context made it obvious that they underlying data structure was an array)

tl;dr: Python "lists" are not "linked lists". But nobody said they were.

I don't see any problem with using "list" to refer to any data structure that is functionally equivalent to a list, regardless of implementation. This is hardly unique to Python: Mathematica's List type (despite the Lisp heritage) is also really an array.

You could easily imagine the implementation being changed to something else (say a VList or unrolled linked list) if someone did some benchmarking and it turned out that it made Python programs 5% faster on average. Then the name "array" would no longer be accurate, and neither would "list" in the narrow, pedantic sense. So using the term "list" in a more abstract sense is perfectly reasonable.

The term "list" also has some (tiny) advantages: it's shorter than "array" or "vector", and it's one less technical term for people learning programming (as I understand, this was one of Guido's design goals).

If we're going to talk about inaccurately named data types, let's start with the ubiquitous use of "integer" to refer to bastardized integers modulo 2^32...

Contrary to people's opinion on this topic I agree to what the author has to say. He states his point in the introduction: " they use terms imprecisely, they write like journalists not scientists".

This is a classic example on how we popularize misuse of certain words/concepts. And Wiki isn't always the best source when we argue on these subjects. I have nothing against anybody using words as they like. But the more we use appropriate terms, the more we can make ourselves better understood.

Most people don't care about semantics but there are some that do. And those who are actively participating in a filed like the scientific one should try to be as clear as possible. Science requires rigor.

Newbie Python question: What does a Python List do that a Ruby Array doesn't do? Regardless of the implementation, this is a question of the abstract behaviour of a data structure. If a Python List is functionally equivalent to an Array (which is a sequence) then why coin it as a "List" ?

Ruby's Array, Python's list, C++'s vector and Java's ArrayList are all the same thing: a variable length collection with an implementation backed by an array that's replaced with a larger array and the information copied over for you if you use all the space. Fundamentally they consist of a primitive array, and a variable containing the length of the collection.

Personally I would usually call the resulting class a list, but that's because most of my programming experience is from Python and Java. I will give that C++'s name is the most explicit (especially since C++ also has std::list which is a linked list).

In C and similar languages however, array refers to something different. In those cases an array is a fixed size collection, i.e. at creation time you need to tell it that your array is 10 items long, and if you need to add an eleventh item, you need to create a new larger array and copy it over in your own code.

In short, Ruby's Array is not functionally equivalent to an array, because it handles a lot more than primitive arrays can. You can't just append to an array, or figure out how many items are in an array without separate knowledge of its size.

To add to the confusion, a python 'array' is a data type which is effectively a fixed type version of a python list. It's still dynamically sized, but it includes the type information once for the entire array rather than per item to make things a bit more efficient.

Thanks for the explanation.

As ever, it's not the name of the structure that's wholly important in determining its purpose; but the interface to which it adheres.

It is weird to call it a list and then use indexing operations on it. But if you just cons stuff onto the front and iterate over the whole structure from time to time, it's perfectly fine to call it one, since if it were a linked list, you wouldn't be misusing the structure.

Reply on news.ycombinator.com