Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #81170 > unrolled thread

Infinitely nested containers

Back to article view | Back to comp.lang.python

Contents

  Infinitely nested containers Gill Shen <gillarete@gmail.com> - 2014-11-20 21:54 -0800
    Re: Infinitely nested containers Marko Rauhamaa <marko@pacujo.net> - 2014-11-21 09:00 +0200
      Re: Infinitely nested containers random832@fastmail.us - 2014-11-21 12:39 -0500
        Re: Infinitely nested containers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-11-22 15:43 +1100
          Re: Infinitely nested containers Chris Angelico <rosuav@gmail.com> - 2014-11-22 15:50 +1100
            Re: Infinitely nested containers Rustom Mody <rustompmody@gmail.com> - 2014-11-21 21:02 -0800
              Re: Infinitely nested containers Chris Angelico <rosuav@gmail.com> - 2014-11-22 16:09 +1100
                Re: Infinitely nested containers Rustom Mody <rustompmody@gmail.com> - 2014-11-21 22:03 -0800
          Re: Infinitely nested containers Ethan Furman <ethan@stoneleaf.us> - 2014-11-22 11:50 -0800
            Re: Infinitely nested containers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-11-23 16:59 +1100
              Re: Infinitely nested containers random832@fastmail.us - 2014-11-23 01:39 -0500
      Re: Infinitely nested containers Chris Angelico <rosuav@gmail.com> - 2014-11-22 04:47 +1100
      Re: Infinitely nested containers random832@fastmail.us - 2014-11-21 12:50 -0500
      Re: Infinitely nested containers Ian Kelly <ian.g.kelly@gmail.com> - 2014-11-21 11:37 -0700
      Re: Infinitely nested containers Zachary Ware <zachary.ware+pylist@gmail.com> - 2014-11-21 13:30 -0600
      Re: Infinitely nested containers Terry Reedy <tjreedy@udel.edu> - 2014-11-22 16:57 -0500
    Re: Infinitely nested containers Chris Angelico <rosuav@gmail.com> - 2014-11-21 18:03 +1100
    Re: Infinitely nested containers Ian Kelly <ian.g.kelly@gmail.com> - 2014-11-21 10:13 -0700

#81170 — Infinitely nested containers

Purely out of curiosity I tried this (on 2.7.3):

>>> ls = []
>>> ls.append(ls)
>>> ls
[[...]]


The list appears to be ... infinitely nested:

>>> ls == ls[0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0]
True


Similar things can be done with non-empty list and dict:

>>> ls2 = [1]
>>> ls2.append(ls2)
>>> ls2
[1, [...]]
>>> ls2 == ls2[1] == ls2[1][1] 
True
>>> d = {}
>>> d[0] = d
>>> d
{0: {...}}
>>> d == d[0] == d[0][0]
True


How is this behavior implemented under the hood? And why is this allowed at all? Is it just a curiosity or can you do something useful with it?

[toc] | [next] | [standalone]

#81173

Gill Shen <gillarete@gmail.com>:

> How is this [nesting] behavior implemented under the hood?

Pointers.

> And why is this allowed at all?

There's no reason not to.

> Is it just a curiosity or can you do something useful with it?

It absolutely does arise every here and there. It's so natural you don't
even pay attention to it.


Marko

[toc] | [prev] | [next] | [standalone]

#81230

On Fri, Nov 21, 2014, at 02:00, Marko Rauhamaa wrote:
> Gill Shen <gillarete@gmail.com>:
> 
> > How is this [nesting] behavior implemented under the hood?
> 
> Pointers.
> 
> > And why is this allowed at all?
> 
> There's no reason not to.

There's no reason not to allow it with tuples, but you can't do it.
Mainly because doing it in a single literal would require special
syntax, whereas you can simply append to a list a reference to itself.

I think I tried on at least one python version and printing the tuple
crashed with a recursion depth error, since it had no special protection
for this case the way list printing does.

[toc] | [prev] | [next] | [standalone]

#81267

random832@fastmail.us wrote:

> On Fri, Nov 21, 2014, at 02:00, Marko Rauhamaa wrote:
>> Gill Shen <gillarete@gmail.com>:
>> 
>> > How is this [nesting] behavior implemented under the hood?
>> 
>> Pointers.
>> 
>> > And why is this allowed at all?
>> 
>> There's no reason not to.
> 
> There's no reason not to allow it with tuples, but you can't do it.
> Mainly because doing it in a single literal would require special
> syntax, whereas you can simply append to a list a reference to itself.

You can't append a list to itself in a single expression, you have to create
the list first.

> I think I tried on at least one python version and printing the tuple
> crashed with a recursion depth error, since it had no special protection
> for this case the way list printing does.


It works fine now (Python 3.3).

py> L = []
py> t = (L, None)
py> L.append(L)
py> L.append(t)  # For good measure.
py> print(t)
([[...], (...)], None)


but yes, in old versions of Python printing self-recursive containers may
break.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#81268

On Sat, Nov 22, 2014 at 3:43 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> random832@fastmail.us wrote:
>
>> There's no reason not to allow it with tuples, but you can't do it.
>> Mainly because doing it in a single literal would require special
>> syntax, whereas you can simply append to a list a reference to itself.
>
> You can't append a list to itself in a single expression, you have to create
> the list first.

It's possible to have a list directly refer to itself:

lst = []
lst.append(lst)

It's not possible, with pure Python code, to create a tuple with a
reference to itself, because you have to create a tuple with a single
expression. Hence the comments about using the C API... and breaking
stuff.

ChrisA

[toc] | [prev] | [next] | [standalone]

#81269

On Saturday, November 22, 2014 10:20:36 AM UTC+5:30, Chris Angelico wrote:
> On Sat, Nov 22, 2014 at 3:43 PM, Steven D'Aprano wrote:
> > random832 wrote:
> >
> >> There's no reason not to allow it with tuples, but you can't do it.
> >> Mainly because doing it in a single literal would require special
> >> syntax, whereas you can simply append to a list a reference to itself.
> >
> > You can't append a list to itself in a single expression, you have to create
> > the list first.
> 
> It's possible to have a list directly refer to itself:
> 
> lst = []
> lst.append(lst)

Thats not a single expression; which is possible with a lazy
evaluation language like Haskell.
Prelude> let ones = 1 : ones
Prelude> ones
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
<until the Control-C>

[toc] | [prev] | [next] | [standalone]

#81271

On Sat, Nov 22, 2014 at 4:02 PM, Rustom Mody <rustompmody@gmail.com> wrote:
> Thats not a single expression; which is possible with a lazy
> evaluation language like Haskell.
> Prelude> let ones = 1 : ones

I'm not sure "lazy evaluation" is the key here, unless it also does
name lookups lazily. What happens if you do this:

let foo = 1 : bar
let bar = 2 : 3
foo

Will that show 1, 2, 3? If so, then sure, lazy eval is what achieved
that - but it's also going to make it hard to track down name errors.

ChrisA

[toc] | [prev] | [next] | [standalone]

#81275

On Saturday, November 22, 2014 10:40:23 AM UTC+5:30, Chris Angelico wrote:
> On Sat, Nov 22, 2014 at 4:02 PM, Rustom Mody  wrote:
> > Thats not a single expression; which is possible with a lazy
> > evaluation language like Haskell.
> > Prelude> let ones = 1 : ones
> 
> I'm not sure "lazy evaluation" is the key here, unless it also does
> name lookups lazily. What happens if you do this:
> 
> let foo = 1 : bar
> let bar = 2 : 3
> foo
> 
> Will that show 1, 2, 3? If so, then sure, lazy eval is what achieved
> that - but it's also going to make it hard to track down name errors.

Prelude> let foo = 1 : bar; bar = 2 : [3]
Prelude> foo
[1,2,3]


Prelude> let foo = 1 : bar; bar = 2 : foo
Prelude> foo
[1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1 <Control-C>

[toc] | [prev] | [next] | [standalone]

#81300

[Multipart message — attachments visible in raw view] — view raw

On 11/21/2014 08:43 PM, Steven D'Aprano wrote:
> random832@fastmail.us wrote:
>> 
>> I think I tried on at least one python version and printing the tuple
>> crashed with a recursion depth error, since it had no special protection
>> for this case the way list printing does.
> 
> It works fine now (Python 3.3).
> 
> py> L = []
> py> t = (L, None)
> py> L.append(L)
> py> L.append(t)  # For good measure.
> py> print(t)
> ([[...], (...)], None)

This is a tuple in a list in a tuple, not a tuple in a tuple.

--
~Ethan~

[toc] | [prev] | [next] | [standalone]

#81330

Ethan Furman wrote:

> On 11/21/2014 08:43 PM, Steven D'Aprano wrote:
>> random832@fastmail.us wrote:
>>> 
>>> I think I tried on at least one python version and printing the tuple
>>> crashed with a recursion depth error, since it had no special protection
>>> for this case the way list printing does.
>> 
>> It works fine now (Python 3.3).
>> 
>> py> L = []
>> py> t = (L, None)
>> py> L.append(L)
>> py> L.append(t)  # For good measure.
>> py> print(t)
>> ([[...], (...)], None)
> 
> This is a tuple in a list in a tuple, not a tuple in a tuple.

Really? I hadn't noticed.

*wink*

It's still a tuple in itself, recursively, and the tuple to str conversion
routine still has to deal with the fact.




-- 
Steven

[toc] | [prev] | [next] | [standalone]

#81337

On Sun, Nov 23, 2014, at 00:59, Steven D'Aprano wrote:
> >> It works fine now (Python 3.3).
> >> 
> >> py> L = []
> >> py> t = (L, None)
> >> py> L.append(L)
> >> py> L.append(t)  # For good measure.
> >> py> print(t)
> >> ([[...], (...)], None)
> > 
> > This is a tuple in a list in a tuple, not a tuple in a tuple.
> 
> Really? I hadn't noticed.
> 
> *wink*
> 
> It's still a tuple in itself, recursively, and the tuple to str
> conversion
> routine still has to deal with the fact.

Does it, or does it punt to the list to str routine?

Anyway, on python 2.7, print and str do not work the same way for
tuples. I'm remembering more about this issue now, and it was _strictly_
on print, not on str.
>>> t
([[...], ([...], None)], None)
>>> print(t)
([[...], ([...], None)], None)
>>> str(t)
'([[...], (...)], None)'


Notice that print never does (...), only [...]. And if it never finds a
[...]?

[toc] | [prev] | [next] | [standalone]

#81232

On Sat, Nov 22, 2014 at 4:39 AM,  <random832@fastmail.us> wrote:
> There's no reason not to allow it with tuples, but you can't do it.
> Mainly because doing it in a single literal would require special
> syntax, whereas you can simply append to a list a reference to itself.
>
> I think I tried on at least one python version and printing the tuple
> crashed with a recursion depth error, since it had no special protection
> for this case the way list printing does.

You can do it in C, I believe - PyTuple_New() followed by
PyTuple_SetItem(x, 0, x) should do it.

ChrisA

[toc] | [prev] | [next] | [standalone]

#81233

On Fri, Nov 21, 2014, at 12:47, Chris Angelico wrote:
> You can do it in C, I believe - PyTuple_New() followed by
> PyTuple_SetItem(x, 0, x) should do it.

Yeah, that's how I did it. I think python 2 crashed and python 3
didn't... or maybe it was the interactive interpreter that crashed and
calling repr didn't, within the same version - I don't remember that
well.

[toc] | [prev] | [next] | [standalone]

#81236

On Fri, Nov 21, 2014 at 10:39 AM,  <random832@fastmail.us> wrote:
> On Fri, Nov 21, 2014, at 02:00, Marko Rauhamaa wrote:
>> Gill Shen <gillarete@gmail.com>:
>>
>> > How is this [nesting] behavior implemented under the hood?
>>
>> Pointers.
>>
>> > And why is this allowed at all?
>>
>> There's no reason not to.
>
> There's no reason not to allow it with tuples, but you can't do it.
> Mainly because doing it in a single literal would require special
> syntax, whereas you can simply append to a list a reference to itself.
>
> I think I tried on at least one python version and printing the tuple
> crashed with a recursion depth error, since it had no special protection
> for this case the way list printing does.

Here's a nice crash. I thought this might similarly produce a
recursion depth error, but no, it's a seg fault!

$ cat test.py
import itertools

l = []
it = itertools.chain.from_iterable(l)
l.append(it)
next(it)
$ python3 test.py
Segmentation fault (core dumped)

[toc] | [prev] | [next] | [standalone]

#81239

On Fri, Nov 21, 2014 at 12:37 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> Here's a nice crash. I thought this might similarly produce a
> recursion depth error, but no, it's a seg fault!
>
> $ cat test.py
> import itertools
>
> l = []
> it = itertools.chain.from_iterable(l)
> l.append(it)
> next(it)
> $ python3 test.py
> Segmentation fault (core dumped)

Would you mind submitting a bug report for that?  Any segfault
produced by pure Python code must be fixed.

-- 
Zach

[toc] | [prev] | [next] | [standalone]

#81303

On 11/21/2014 2:30 PM, Zachary Ware wrote:
> On Fri, Nov 21, 2014 at 12:37 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> Here's a nice crash. I thought this might similarly produce a
>> recursion depth error, but no, it's a seg fault!
>>
>> $ cat test.py
>> import itertools
>>
>> l = []
>> it = itertools.chain.from_iterable(l)
>> l.append(it)
>> next(it)
>> $ python3 test.py
>> Segmentation fault (core dumped)
>
> Would you mind submitting a bug report for that?  Any segfault
> produced by pure Python code must be fixed.

This is too important to lose.
http://bugs.python.org/issue22920


-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#81175

On Fri, Nov 21, 2014 at 4:54 PM, Gill Shen <gillarete@gmail.com> wrote:
> How is this behavior implemented under the hood? And why is this allowed at all? Is it just a curiosity or can you do something useful with it?

Simple: The list contains itself. When you dereference the list, you
get back the original list. It does have value; you just have to be
careful of any recursive operation like printing it out - the repr()
for a list carefully checks for this.

ChrisA

[toc] | [prev] | [next] | [standalone]

#81229

On Thu, Nov 20, 2014 at 10:54 PM, Gill Shen <gillarete@gmail.com> wrote:
> How is this behavior implemented under the hood? And why is this allowed at all? Is it just a curiosity or can you do something useful with it?

Reference cycles are common in Python and other OO languages. For
example, adding a widget to a window; the window contains references
to its child widgets, and it's probably useful for the widgets to know
what their parents are, so they would hold references back.

A list containing itself is similarly a reference cycle. I don't know
off-hand of any use for this specific case, but it's just a slightly
tighter cycle than normal.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web