title: How do I determine whether a container is infinitely recursive and find its smallest unique container?
body: <p>I was reading <a href="https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python">Flatten (an irregular) list of lists</a> and decided to adopt it as a Python exercise - a small function I'll occasionally rewrite without referring to the original, just for practice. The first time I tried this, I had something like the following:</p>
  
  <pre><code>def flat(iterable):
      try:
          iter(iterable)
      except TypeError:
          yield iterable
      else:
          for item in iterable:
              yield from flatten(item)
  </code></pre>
  
  <p>This works fine for basic structures like nested <code>list</code>s containing numbers, but strings crash it because the first element of a string is a single-character string, the first element of which is itself, the first element of which is itself again, and so on. Checking the question linked above, I realized that that explains the check for strings. That gave me the following:</p>
  
  <pre><code>def flatter(iterable):
      try:
          iter(iterable)
          if isinstance(iterable, str):
              raise TypeError
      except TypeError:
          yield iterable
      else:
          for item in iterable:
              yield from flatten(item)
  </code></pre>
  
  <p>Now it works for strings as well. However, I then recalled that a <code>list</code> can contain references to itself.</p>
  
  <pre><code>&gt;&gt;&gt; lst = []
  &gt;&gt;&gt; lst.append(lst)
  &gt;&gt;&gt; lst
  [[...]]
  &gt;&gt;&gt; lst[0][0][0][0] is lst
  True
  </code></pre>
  
  <p>So, a string isn't the only type that could cause this sort of problem. At this point, I started looking for a way to guard against this issue without explicit type-checking.</p>
  
  <p>The following <code>flattener.py</code> ensued. <code>flattish()</code> is a version that just checks for strings. <code>flatten_notype()</code> checks whether an object's first item's first item is equal to itself to determine recursion. <code>flatten()</code> does this and then checks whether either the object or its first item's first item is an instance of the other's type. The <code>Fake</code> class basically just defines a wrapper for sequences. The comments on the lines that test each function describe the results, in the form <code>should be `desired_result` [&gt; `undesired_actual_result`]</code>. As you can see, each fails in various ways on <code>Fake</code> wrapped around a string, <code>Fake</code> wrapped around a <code>list</code> of integers, single-character strings, and multiple-character strings.</p>
  
  <pre><code>def flattish(*i):
      for item in i:
          try: iter(item)
          except: yield item
          else:
              if isinstance(item, str): yield item
              else: yield from flattish(*item)
  
  class Fake:
      def __init__(self, l):
          self.l = l
          self.index = 0
      def __iter__(self):
          return self
      def __next__(self):
          if self.index &gt;= len(self.l):
              raise StopIteration
          else:
              self.index +=1
              return self.l[self.index-1]
      def __str__(self):
          return str(self.l)
  
  def flatten_notype(*i):
      for item in i:
          try:
              n = next(iter(item))
              try:
                  n2 = next(iter(n))
                  recur = n == n2
              except TypeError:
                  yield from flatten(*item)
              else:
                  if recur:
                      yield item
                  else:
                      yield from flatten(*item)
          except TypeError:
              yield item
  
  def flatten(*i):
      for item in i:
          try:
              n = next(iter(item))
              try:
                  n2 = next(iter(n))
                  recur = n == n2
              except TypeError:
                  yield from flatten(*item)
              else:
                  if recur:
                      yield item if isinstance(n2, type(item)) or isinstance(item, type(n2)) else n2
                  else:
                      yield from flatten(*item)
          except TypeError:
              yield item
  
  
  f = Fake('abc')
  
  print(*flattish(f)) # should be `abc`
  print(*flattish((f,))) # should be `abc` &gt; ``
  print(*flattish(1, ('a',), ('bc',))) # should be `1 a bc`
  
  f = Fake([1, 2, 3])
  
  print(*flattish(f)) # should be `1 2 3`
  print(*flattish((f,))) # should be `1 2 3` &gt; ``
  print(*flattish(1, ('a',), ('bc',))) # should be `1 a bc`
  
  f = Fake('abc')
  print(*flatten_notype(f)) # should be `abc`
  print(*flatten_notype((f,))) # should be `abc` &gt; `c`
  print(*flatten_notype(1, ('a',), ('bc',))) # should be `1 a bc` &gt; `1 ('a',) bc`
  
  f = Fake([1, 2, 3])     
  
  print(*flatten_notype(f)) # should be `1 2 3` &gt; `2 3`
  print(*flatten_notype((f,))) # should be `1 2 3` &gt; ``
  print(*flatten_notype(1, ('a',), ('bc',))) # should be `1 a bc` &gt; `1 ('a',) bc`
  
  f = Fake('abc')
  print(*flatten(f)) # should be `abc` &gt; `a`
  print(*flatten((f,))) # should be `abc` &gt; `c`
  print(*flatten(1, ('a',), ('bc',))) # should be `1 a bc`
  
  f = Fake([1, 2, 3])     
  
  print(*flatten(f)) # should be `1 2 3` &gt; `2 3`
  print(*flatten((f,))) # should be `1 2 3` &gt; ``
  print(*flatten(1, ('a',), ('bc',))) # should be `1 a bc`
  </code></pre>
  
  <p>I've also tried the following with the recursive <code>lst</code> defined above and <code>flatten()</code>:</p>
  
  <pre><code>&gt;&gt;&gt; print(*flatten(lst))
  [[...]]
  &gt;&gt;&gt; lst.append(0)
  &gt;&gt;&gt; print(*flatten(lst))
  [[...], 0]
  &gt;&gt;&gt; print(*list(flatten(lst))[0])
  [[...], 0] 0
  </code></pre>
  
  <p>As you can see, it fails similarly to <code>1 ('a',) bc</code> as well as in its own special way.</p>
  
  <p>I read <a href="https://stackoverflow.com/questions/3109289/how-can-python-function-access-its-own-attributes">how can python function access its own attributes?</a> thinking that maybe the function could keep track of every object it had seen, but that wouldn't work either because our <code>lst</code> contains an object with matching identity and equality, strings contain objects that may only have matching equality, and equality isn't enough due to the possibility of something like <code>flatten([1, 2], [1, 2])</code>.</p>
  
  <p>Is there any reliable way (i.e. doesn't simply check known types, doesn't require that a recursive container and its containers all be of the same type, etc.) to check whether a container holds iterable objects with potential infinite recursion, and reliably determine the smallest unique container? If there is, please explain how it can be done, why it is reliable, and how it handles various recursive circumstances. If not, please explain why this is logically impossible.</p>