Confusing […] List in Python: What is it?

Question

So I was writing up a simple binary tree in Python and came across [...]

I don't believe this to be related to the Ellipsis object, more it seems to have something to do with an infinity loop (due to Python's shallow copy?). The source of this infinity loop and why it doesn't get expanded while expanding when accessed is something I'm completely lost to, however

>>> a
[[[[[], [], 8, 3], [[], [], 3, 2], 6, 3], [], 1, 4], [[], [], -4, 2], 0, 0]
>>> Keys(a)#With a+b
[0, 1, 6, 8, 3, -4]
>>> Keys(a)#With [a,b]
[8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...]]
>>> Keys(a)[1]#??
[8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...], 8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...]]

Version using a+b

def Keys(x,y=[]):
    if len(x):y+=[x[2]]+Keys(x[0],y)+Keys(x[1],y)#Though it seems I was using y=y[:]+, this actually outputs an ugly mess
    return y

version using [a,b]

def Keys(x,y=[]):
    if len(x):y+=[x[2],Keys(x[0],y),Keys(x[1],y)]
    return y

So what exactly is [...]?

Answer 1

The issue is because one of the list element is referencing the list itself. So if an attempt to print all the elements is made then it would never end.

Illustration:

x = range(3)
x.append(x)
x[3][3][3][3][3][0] = 5
print x

Output:

[5, 1, 2, [...]]

x[3] is a referring to x itself. Same goes for x[3][3].

This can be visualized better here

Answer 2

I don't believe this to be related to the Ellipsis object, more it seems to have something to do with an infinity loop (due to Python's shallow copy?). The source of this infinity loop and why it doesn't get expanded while expanding when accessed is something I'm completely lost to, however

Look at the following code:

>>> a = [0]
>>> a.append(a)
>>> print a
[0, [...]]

How is Python supposed to print a? It is a list that contains a zero and a reference to itself. Hence it is a list that contains a zero and a reference to a list

[0, [...]]

which in turn contains a zero and a reference to a list

[0, [0, [...]]]

which in turn contains a zero and a reference to a list, and so on, recursively:

[0, [0, [0, [...]]]]
[0, [0, [0, [0, [...]]]]]
[0, [0, [0, [0, [0, [...]]]]]]
...

There is nothing wrong with the recursive data structure itself. The only problem is that it cannot be displayed, for this would imply an infinite recursion. Hence Python stops at the first recursion step and deals with the infinity issue printing only the ellipsis, as was pointed out in previous answers.

Answer 3

I believe, that your 'tree' contains itself, therefore it contains cycles.

Try this code:

   a = [1,2,3,4]
   print a
   a.append(a)
   print a

The first print outputs:

  [1,2,3,4]

while the second:

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

The reason is using

 def Keys(x,y=[]):
 

This is wrong and evil. List is a mutable object, and when used as a default parameter, it is preserved between function calls. So each y += "anything" operation adds to the same list (in all function calls, and since the function is recursive...)

---

See the Effbot or Devshed for more details on mutable objects passed as default values for functions.

Answer 4

EDIT: As mentioned above, this isn't the Ellipsis object, but the result of a looped list. I jumped the gun here. Knowing about the Ellipsis object is a good bit of back shelf knowledge should you find an Ellipsis in some actual code, rather than the output.

---

The Ellipsis object in Python is used for extended slice notation. It's not used in current Python core libraries, but is available for developers to define in their own libraries. For example, NumPy (or SciPy) use this as part of their array object. You'll need to look at the documentation for tree() to know exactly how Ellipsis behaves in this object.

From Python documentation:

3.11.8 The Ellipsis Object

This object is used by extended slice notation (see the Python Reference Manual). It supports no special operations. There is exactly one ellipsis object, named Ellipsis (a built-in name).

It is written as Ellipsis.

Answer 5

If you would have used a PrettyPrinter, the output would had been self explanatory

>>> l = [1,2,3,4]
>>> l[0]=l
>>> l
[[...], 2, 3, 4]
>>> pp = pprint.PrettyPrinter(indent = 4)
>>> pp.pprint(l)
[<Recursion on list with id=70327632>, 2, 3, 4]
>>> id(l)
70327632

In other words its something like

Answer 6

I don't understand your code above, but the [...] I think is the Python interpreter skipping infinite data structures. For example:

>>> a = [0, 1]
>>> a[0] = a
>>> a
[[...], 1]

It looks like your tree structure is becoming looped.

The answers about slice objects are beside the point.