如何判断一个容器是否无限递归并找到其最小的唯一容器？

我正在读书展平（不规则的）列表列表 https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python并决定将其作为 Python 练习——我偶尔会重写一个小函数，而不参考原始函数，只是为了练习。我第一次尝试这个时，我遇到了类似以下的情况：

def flat(iterable):
    try:
        iter(iterable)
    except TypeError:
        yield iterable
    else:
        for item in iterable:
            yield from flatten(item)

这对于嵌套等基本结构非常有效lists 包含数字，但字符串会使它崩溃，因为字符串的第一个元素是单字符字符串，其第一个元素是其自身，其第一个元素又是其自身，依此类推。检查上面链接的问题，我意识到这解释了字符串的检查。这给了我以下内容：

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)

现在它也适用于字符串。不过，我随即想起，有一个list可以包含对其自身的引用。

>>> lst = []
>>> lst.append(lst)
>>> lst
[[...]]
>>> lst[0][0][0][0] is lst
True

因此，字符串并不是唯一可能导致此类问题的类型。此时，我开始寻找一种无需显式类型检查即可防范此问题的方法。

下列flattener.py随后。flattish()是一个仅检查字符串的版本。flatten_notype()检查对象的第一项是否等于其自身以确定递归。flatten()执行此操作，然后检查该对象或其第一项的第一项是否是另一个类型的实例。这Fake类基本上只是定义序列的包装器。测试每个函数的行上的注释以以下形式描述结果should be `desired_result` [> `undesired_actual_result`]。正如您所看到的，每种方法都以不同的方式失败Fake缠绕在一根绳子上，Fake缠绕在一个list整数、单字符字符串和多字符字符串。

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 >= 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` > ``
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` > ``
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` > `c`
print(*flatten_notype(1, ('a',), ('bc',))) # should be `1 a bc` > `1 ('a',) bc`

f = Fake([1, 2, 3])     

print(*flatten_notype(f)) # should be `1 2 3` > `2 3`
print(*flatten_notype((f,))) # should be `1 2 3` > ``
print(*flatten_notype(1, ('a',), ('bc',))) # should be `1 a bc` > `1 ('a',) bc`

f = Fake('abc')
print(*flatten(f)) # should be `abc` > `a`
print(*flatten((f,))) # should be `abc` > `c`
print(*flatten(1, ('a',), ('bc',))) # should be `1 a bc`

f = Fake([1, 2, 3])     

print(*flatten(f)) # should be `1 2 3` > `2 3`
print(*flatten((f,))) # should be `1 2 3` > ``
print(*flatten(1, ('a',), ('bc',))) # should be `1 a bc`

我还尝试了以下递归lst上面定义和flatten():

>>> print(*flatten(lst))
[[...]]
>>> lst.append(0)
>>> print(*flatten(lst))
[[...], 0]
>>> print(*list(flatten(lst))[0])
[[...], 0] 0

如您所见，它的失败类似于1 ('a',) bc以及以自己特殊的方式。

I read python函数如何访问自己的属性？ https://stackoverflow.com/questions/3109289/how-can-python-function-access-its-own-attributes认为也许该函数可以跟踪它所看到的每个对象，但这也行不通，因为我们lst包含具有匹配标识和相等性的对象，字符串包含可能仅具有匹配相等性的对象，并且由于可能存在以下情况，相等性是不够的flatten([1, 2], [1, 2]).

是否有任何可靠的方法（即不简单地检查已知类型，不要求递归容器及其容器都属于同一类型等）来检查容器是否包含具有潜在无限递归的可迭代对象，以及可靠地确定最小的唯一容器？如果有，请解释它是如何做到的，为什么它是可靠的，以及它如何处理各种递归情况。如果不是，请解释为什么这在逻辑上是不可能的。

我认为没有可靠的方法来确定任意可迭代是否是无限的。我们能做的最好的事情就是从这样一个可迭代对象中无限地产生原语，而不耗尽堆栈，例如：

from collections import deque

def flat(iterable):

    d = deque([iterable])

    def _primitive(x):
        return type(x) in (int, float, bool, str, unicode)

    def _next():
        x = d.popleft()
        if _primitive(x):
            return True, x
        d.extend(x)
        return False, None

    while d:
        ok, x = _next()
        if ok:
            yield x


xs = [1,[2], 'abc']
xs.insert(0, xs)

for p in flat(xs):
    print p

上面对“原始”的定义是原始的，但是肯定可以改进。