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

Question

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.

Schoonmaker

A simpler example would be p = [1]; p[0] = p. – Rennes

I think this is a duplicate of What does […] (an ellipsis) in a list mean in Python?, although the question (and answers) are better in this question. – Crape

Dreampie is smart ` >>> p[1:1] = [p] >>> p 3: [1, <Recursion on list with id=3074777548>, 2] >>> ` provide the exact detail – Juanitajuanne

@RahulGautam Didn't get this p 3: [1, <Recursion on list with id=3074777548>, 2]. What did you run? – Schoonmaker

id=3074777548 is the id of p so its easy to understand that its referring to itself. Anyway very nice question @Zel – Juanitajuanne

I use dreampie.org – Juanitajuanne

@Zel its python shell like IDLE or simple python >>>. follow the link – Juanitajuanne

@AseemBansal: The link worked fine for me and using Dreampie I got the same output as Rahul Gautam. – Erdei

Answer 1

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

Litotes

So is it taking infinte memory? I know that cannot be possible. How is it represented and what's its use? – Schoonmaker

@Zel: List elements are references. The second element is a reference to the list itself. – Kolomna

Python it identified it as an infinite loop of references, so it decided to cut it short, it's not really infinite. And no, it's not really useful besides a thought experiment :) – Thyroiditis

There are... a few uses for infinitely recursive structures. But not many. – Kolomna

@IgnacioVazquez-Abrams Some examples would be useful. – Schoonmaker

Answer 2

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

Stuccowork

You can find the contents of the [1, [2, [...], 3]] like this: x[1] = [2, [...], 3] and y[1] = [2, 1, [...]], 3]. This means that x consists of a 1 and then repeating 2s, whereas y consists of alternating 1s and 2s. – Skivvy

@csharpler: of course you can distinguish the two by analyzing the content, however they are printed with the same representation. In Common Lisp format instead they would be #(1 #1=#(2 #1# 3)) for x and #1=#(1 #(2 #1# 3)) for y. – Stuccowork

@BurhanKhalid: inkscape for the first and gimp for the second (because I threw away the svg) – Stuccowork

How did you create these illustrations? Is there a visualisation library? – Introrse

@csharpler: you cannot create an "infinite list" in Python because lists are indeed resizable arrays, not linked lists. An "infinite list" in Common Lisp could instead be created with #1=(1 . #1#). – Stuccowork

+1 for illustrations and the explanation regarding the apparent ambiguity. The explanation regarding "what it is" is nice. – Schoonmaker

+ if you wants to draw acsii-diagram like this try: Asiiflow – Mumble

Answer 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

Graig

Answer 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.

Gallicanism

Simpler dictionary example: a = {}; a['a'] = a; print a['a']['a']['a'] – Touchdown

For me, instead of "..." it shows "<Recursion on dict with id=___>" – Pettifogger

@SolomonUcko You're probably using IPython which automatically uses pprint to print things. If you type %pprint to toggle pretty-printing off, it will show .... – Gallicanism

Answer 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

Amorita

I haven't been able to understand this. Tried to run these commands but there are errors. – Schoonmaker

@Zel: Well, you have to add OPs code before it so that p is declared. – Jenna

@Jenna Still this doesn't make any sense to me with respect to the question. – Schoonmaker

@Zel: Well, I'm not sure how helpful it is myself, but Firegun says that p (and therefore p[1], represented as [...]) is a fixpoint of the function f. IMHO, this is a possible answer of the question "What is [...]?" in this case. – Jenna

I had the same error issue because I had tried this example after trying the simpler p = [1]; p[0] = p example which needs f = lambda x:x[0] to work. It is an example of a fix point, but I have not yet been able to see how knowing this is useful. The real value of the fix point is arriving at it from some other point in a recursive or iterative manner. An example that shows how to use the list structure of the original question to create the Y combinator would be helpful if it is possible. – Aerostation

Fixed-point combinators are related to functional language as well -- but are a slightly different topic. Their main use is to produce anonymous recursive functions (to speak Python: "recursive lambda"). Here, the question was about recursive data structures. – Graig

q = lambda: q makes an infinitely callable lambda – Doyledoyley