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

Question

我正在阅读 Flatten (an irregular) list of lists并决定将它作为一个 Python 练习——我偶尔会在不引用原始函数的情况下重写一个小函数，只是为了练习。我第一次尝试这个时，我有类似以下的内容:

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

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

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 以及它自己的特殊方式。

我读了how can python function access its own attributes?认为也许该函数可以跟踪它看到的每个对象，但这也行不通，因为我们的 lst 包含一个具有匹配标识和相等性的对象，字符串包含可能只具有匹配相等性的对象，并且由于可能出现类似 flatten([1, 2], [1, 2]) 的情况，平等还不够。

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

Answer 1

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

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

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