Почему filter работает не так как ожидается?

Question

[Влад]

Всем привет.

Есть следующий код, который отвечают сбалансированы ли данные скобки (аргумент caps) в строке (аргумент source):

# Python 3.x
def is_balanced(source, caps):
    source = filter(lambda x: x in caps, source)
    caps = dict(zip(caps[::2], caps[1::2]))
    stack = []
    for cap in source:
        if stack and cap == caps.get(stack[-1], ""):
            stack.pop()
        else:
            stack.append(cap)
    return not stack

На простом примере
is_balanced("(Sensei says yes!)", "()")
выдает False.

Прогнался по строчкам в дебаггере и обнаружил что проблема в том, что cap в цикле никогда не будет равен ")" o_o.

Если же избавиться от итератора, возвращаемого фильтром:

...
source = list(filter(lambda x: x in caps, source))
...

то все работает прекрасно.

И вопрос: почему так? Что я не понимаю?

Answer 1

[DeepBlue]

Переменная caps перегружена: изначально она означает строку, содержащую скобки, а затем словарь. Из-за этого filter при выполнении в строке "for cap in source:" проверяет, есть ли символ среди ключей словаря, а не в исходной строке, а закрывающей скобки там нет. Назовите словарь по-другому, и всё заработает:

def is_balanced(source, caps):
    source = filter(lambda x: x in caps, source)
    caps_dict = dict(zip(caps[::2], caps[1::2]))
    stack = []
    for cap in source:
        if stack and cap == caps_dict.get(stack[-1], ""):
            stack.pop()
        else:
            stack.append(cap)
    return not stack

Comments

[Влад]

Точно, спасибо!

Answer 2

[Александр]

Написал ответ и только потом заметил, что вы немного изменили вопрос. Но решил ответ не менять.

В третьей строчке (где фильтруется source), я обернул фильтр в list().
Вот так:

source = list(filter(lambda x: x in caps, source))

И у меня всё заработало.

Не уверен, но сильно подозреваю, что дело вот в чём:

filter() сам по себе возвращает не список, а объект типа "фильтр". То есть там пока ещё не сама отфильтрованная последовательность, а только инструкции о том, что и как фильтровать.
И после этого вы меняете caps, который участвует в фильтрации. Соответственно, фильтрация будет происходить уже по-другому.

Я немножко погонял фильтр на похожих примерах - похоже, моя догадка верна.
Если в фильтре в лямбде мы проверяем присутствие переменной в списке, а потом меняем список, то фильтр будет работать уже по-другому.

Comments

[Влад]

Да, Вы правы, фильтр возвращает итератор, который считает "на лету". Но если обернуть фильтр в список, то он сразу всю последовательность и обсчитает, с немодифицированным caps'ом. Тем не менее, спасибо за ответ!