Я читал Сгладить (нерегулярный) список списков и решил принять его как упражнение на 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)
Теперь он работает и для строк. Тем не менее, я тогда вспомнил, что 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]).
Есть ли какой-либо надежный способ (т.е. не просто проверять известные типы, не требует, чтобы рекурсивный контейнер и его контейнеры были одного типа и т.д.), чтобы проверить, содержит ли контейнер итерируемые объекты с потенциальным бесконечным рекурсии и надежно определить самый маленький уникальный контейнер? Если есть, объясните, как это можно сделать, почему оно надежное и как оно обрабатывает различные рекурсивные обстоятельства. Если нет, объясните, почему это логически невозможно.
