What do ellipsis [...] mean in a list?

I was playing around in python. I used the following code in IDLE:

p  = [1, 2]
p[1:1] = [p]
print p

The output was:

[1, [...], 2]

What is this […]? Interestingly I could now use this as a list of list of list up to infinity i.e.

p[1][1][1]....

I could write the above as long as I wanted and it would still work.

EDIT:

• How is it represented in memory?
• What's its use? Examples of some cases where it is useful would be helpful.
• Any link to official documentation would be really useful.

Solution 1:

This is what your code created

It's a list where the first and last elements are pointing to two numbers (1 and 2) and where the middle element is pointing to the list itself.

In Common Lisp when printing circular structures is enabled such an object would be printed as

#1=#(1 #1# 2)

meaning that there is an object (labelled 1 with #1=) that is a vector with three elements, the second being the object itself (back-referenced with #1#).

In Python instead you just get the information that the structure is circular with [...].

In this specific case the description is not ambiguous (it's backward pointing to a list but there is only one list so it must be that one). In other cases may be however ambiguous... for example in

[1, [2, [...], 3]]

the backward reference could either point to the outer or to the inner list. These two different structures printed in the same way can be created with

x = [1, [2, 3]]
x[1][1:1] = [x[1]]

y = [1, [2, 3]]
y[1][1:1] = [y]

print(x)
print(y)

and they would be in memory as

Solution 2:

It means that you created an infinite list nested inside itself, which can not be printed. p contains p which contains p ... and so on. The [...] notation is a way to let you know this, and to inform that it can't be represented! Take a look at @6502's answer to see a nice picture showing what's happening.

Now, regarding the three new items after your edit:

• This answer seems to cover it
• Ignacio's link describes some possible uses
• This is more a topic of data structure design than programming languages, so it's unlikely that any reference is found in Python's official documentation

Solution 3:

To the question "What's its use", here is a concrete example.

Graph reduction is an evaluation strategy sometime used in order to interpret a computer language. This is a common strategy for lazy evaluation, notably of functional languages.

The starting point is to build a graph representing the sequence of "steps" the program will take. Depending on the control structures used in that program, this might lead to a cyclic graph (because the program contains some kind of "forever" loop -- or use recursion whose "depth" will be known at evaluation time, but not at graph-creation time)...

In order to represent such graph, you need infinite "data structures" (sometime called recursive data structures), like the one you noticed. Usually, a little bit more complex though.

If you are interested in that topic, here is (among many others) a lecture on that subject:
http://undergraduate.csse.uwa.edu.au/units/CITS3211/lectureNotes/14.pdf

Solution 4:

We do this all the time in object-oriented programming. If any two objects refer to each other, directly or indirectly, they are both infinitely recursive structures (or both part of the same infinitely recursive structure, depending on how you look at it). That's why you don't see this much in something as primitive as a list -- because we're usually better off describing the concept as interconnected "objects" than an "infinite list".

You can also get ... with an infinitely recursive dictionary. Let's say you want a dictionary of the corners of a triangle, where each value is a dictionary of the other corners connected to that corner. You could set it up like this:

a = {}
b = {}
c = {}
triangle = {"a": a, "b": b, "c": c}
a["b"] = b
a["c"] = c
b["a"] = a
b["c"] = c
c["a"] = a
c["b"] = b

Now if you print triangle (or a or b or c for that matter), you'll see it's full of {...} because any two corners are referring to back to each other.

Solution 5:

As I understood, this is an example of fixed point

p  = [1, 2]
p[1:1] = [p]
f = lambda x:x[1]
f(p)==p
f(f(p))==p