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

Question

我正在阅读Flatten(一个不规则的)列表列表,并决定采用它作为Python练习 - 我偶尔会重写一个小函数,而不是参考原文,只是为了练习.我第一次尝试这个,我有类似以下内容:

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

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

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)

现在它也适用于字符串.但是,我随后回忆起a 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和它自己的特殊方式失败.

我看了python函数如何访问自己的属性？认为函数可能跟踪它看到的每个对象,但这不会起作用,因为我们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

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