Os Podres do Python: for-else

2015.01.12

Felizmente o for-else é pouco conhecido mas de vez em quando encontro pessoas convencidas de que vale a pena ensinar esse recurso para iniciantes. Eu discordo desse ponto de vista e nesse post apresento alguns argumentos para considerar o for-else um dos grandes podres do Python.

Nota: Tudo o que eu falar aqui sobre o for-else vale também para o while-else. O else nesses dois casos funcionam da mesma forma.more on matched betting

1. É um mecanismo bastante anti-intuitivo

lista = [] 

for x in lista:
    print(‘dentro do bloco do for’)
    print(x)
else:
    print(‘dentro do bloco do else’)

# SAÍDA:
# dentro do bloco do else

Invariavelmente quando alguém encontra esse else pela primeira vez, naturalmente pensa no como o if-else funciona.

lista = []
x = 1729 

if x in lista:
    print(‘dentro do bloco do if’)
    print(x)
else:
    print(‘dentro do bloco do else’)

# SAÍDA:
# dentro do bloco do else

Nesses dois exemplos as saídas são a mesma. Isso significa então que a estrutura é similar ao if-else e que posso usar o bloco do else para ser executado caso a lista seja vazia, certo? Errado.

lista = [1729]
x = 1729 

if x in lista:
    print(‘dentro do bloco do if’)
    print(x)
else:
    print(‘dentro do bloco do else’)

# SAÍDA:
# dentro do bloco do if
# 1729

 

lista = [1729

for x in lista:
    print(‘dentro do bloco do for’)
    print(x)
else:
    print(‘dentro do bloco do else’)

# SAÍDA:
# dentro do bloco do for
# 1729
# dentro do bloco do else

Então aqui está demonstrado que o else associado ao for tem um modelo de funcionamento diferente do que normalmente esperaríamos do else associado ao if.

Mas a confusão ainda não acabou, é aqui onde a maioria das pessoas param de estudar e se convencem de que o else sempre será executado no final de todo for. Se isso fosse verdade o uso do else seria completamente redundante, afinal para todo código da forma:

for elemento in iterável:
    # …
    # código aqui
    # …
else:
    print(‘blablabla’)

…Eu poderia escrever a mesma coisa de uma forma mais direta e óbvia assim:

for elemento in iterável:
    # …
    # código aqui
    # …
print(‘blablabla’)

O que não é verdade. Voltando no exemplo que estávamos trabalhando antes, veja o que acontece se colocarmos um break.

lista = [1729

for x in lista:
    print(‘dentro do bloco do for’)
    print(x)
    if x == 1729:
        break
else:
    print(‘dentro do bloco do else’)

# SAÍDA:
# dentro do bloco do for
# 1729

O bloco do else não foi executado.

A ideia é que o else faz parte do laço. Então o break não apenas sai do bloco do for, o break sai do laço.

Então uma conclusão importante aqui é que só faz sentido usar o for-else se você estiver usando break.

Agora que (talvez) você tenha entendido como o for-else funciona, o próximo problema fica bem óbvio…

2. O nome “else” foi um equívoco

Acredito que mesmo os grandes proponentes do uso do for-else concordam que “else” foi um nome infeliz pra se dar nesse contexto. Um nome sugerido por várias pessoas para substituir “else” nesse contexto é “nobreak”. Isso resolveria o típico erro de compará-lo com o else do if-else que conhecemos tão bem. Qualquer um ao ler “nobreak” daria um passo para trás e limparia a mente de preconceitos para aprender esse mecanismo novo. Além de já dar uma pista de que ele tem alguma relação importante com o break.

Vou aproveitar e ressaltar esse fato aqui: Python não é uma linguagem perfeita. Python não é um presente que deuses perfeitos da programação deram para nós que somos meros mortais usuários da linguagem. Caras como o Guido van Rossum e Don Knuth também cometem erros como se pode ver.

Mas eu quero ir além, vou ser mais radical e afirmar que…

3. É totalmente inútil na prática

Aqui está o único exemplo mais ou menos prático que já vi de for-else. Todos os outros parecem ser pequenas variações dele.

def busca(lista, alvo):
    encontrado = False
    for i, elemento in enumerate(lista):
        if elemento == alvo:
            encontrado = True
            break
    if not encontrado:
        return –1
    return i

A ideia dessa função é buscar numa lista um certo alvo e retornar o índice i correspondente. Se alvo não estiver dentro da lista a função retorna -1. O funcionamento é bastante similar ao str.find().

Não vejo problemas com este código. Estamos usando encontrado como uma variável de flag e não tem nada de errado com isso. É bastante claro porque é universalmente idiomático.

O argumento para se usar o for-else aqui é eliminar esse uso de flag.

def busca(lista, alvo):
    for i, elemento in enumerate(lista):
        if elemento == alvo:
            break
    else:
        return –1
    return i

A não ser que você já seja um macaco velho de python, esse código não é imediatamente óbvio. Mas o argumento principal é que é mais eficiente, como se uma mísera variável de flag fosse um peso considerável dentro do contexto de um programa feito em python…

Mas isso não importa se você considerar esta alternativa:

def busca(lista, alvo):
    for i, elemento in enumerate(lista):
        if elemento == alvo:
            return i
    return –1

Eficiente. Menos linhas de código. Universalmente fácil de entender. Não tem como deixar melhor que isso.

Se você lembrar de quebrar seu código em funções e que return é um comando poderoso então você terá muitas oportunidades de simplificar o código assim. Não é possível eliminar todo uso de flags e breaks mas eu acredito que com essa técnica você possa cobrir qualquer uso de for-else.

Se você conhece um caso onde o for-else é melhor do que usar uns returns estrategicamente posicionados por favor me mostre para eu reconsiderar minha opinião. Até hoje não vi.

4. Não é suficientemente expressivo e vai contra a filosofia da linguagem

Em Ruby existe o comando unless que na prática poderia ser considerado inútil. Pois no lugar dele você poderia muito bem se limitar a usar apenas os bem conhecidos if e else. Mas ao contrário do for-else do Python, eu acredito que o unless do Ruby é consideravelmente expressivo. Em alguns casos a leitura do código flui de uma maneira mais natural. Eu não sinto a mesma coisa com o for-else, porque este não é um mecanismo inspirado pela forma que conversamos em linguagem natural como o unless. Pelo contrário, o for-else veio de uma lógica bem particular de linguagem de máquina.

Expressividade é importante na filosofia de Ruby, é celebrado ter várias maneiras alternativas de fazer a mesma coisa. Em contraste, Python tem uma filosofia extremamente aversa a isso.

Explicit is better than implicit.
Simple is better than complex.

There should be one– and preferably only one –obvious way to do it.

If the implementation is hard to explain, it’s a bad idea.

Não sou o maior fã de discutir o que é considerado “pythonico” ou não, mas dessa vez vou abrir uma exceção e apontar que o for-else claramente vai contra essas 4 linhas do The Zen of Python.

Muita gente gostaria que o Python tivesse alguma espécie de mecanismo como o “do-while” mas toda tentativa é barrada porque vai contra a filosofia. Se me perguntassem pra escolher entre o do-while e o for-else, eu não hesitaria em ficar com o do-while.

O for-else é legado de uma época onde a filosofia do Python não estava amadurecida do jeito que está hoje.

Conclusão

Resumindo o que penso do for-else:

1. É um mecanismo bastante anti-intuitivo
2. O nome “else” foi um equívoco
3. É totalmente inútil na prática
4. Não é suficientemente expressivo e vai contra a filosofia da linguagem

 

Eu não sou um rebelde! Raymond Hettinger que é um lunático pra pensar que for-else é “trivialmente fácil de explicar”.

Python é a única linguagem que possui esse mecanismo do for-else. E eu aposto que vai continuar assim.

Configuração do vim para Python

2014.09.30

Para aqueles que estão começando e são desequilibrados mentalmente a ponto de preferirem escrever Python dentro do vim no ano de 2014… Aqui está uma configuração que escrevi com o que considero mais ou menos o essencial para esse propósito.

vim_config.tgz

Para instalar basta colocar o arquivo .vimrc e a pasta .vim dentro do seu home (/home/<nome-do-usuário>).

Essa configuração inclui um script melhor de syntax highlighting e recursos melhores para indentação. Como usei o Vundle para fazer o gerenciamento dos scripts, você poderá eventualmente atualizar os scripts com o comando :BundleUpdate.

Não tem nada a ver com python mas inclui também o vim-airline porque todo mundo gosta dessas barrinhas.

Certificate Verification for Costas Arrays

2014.04.25

If you never heard of Costas arrays before you may want to watch this video.

First of all, I want to be clear with the way that I’m saying “Costas arrays” but I’m not really working with arrays. It’s more common to think of them as permutations.

This is the definition that I found the easiest to understand:

Definition Let f\colon [n] \rightarrow [n]. f has the Costas property iff

    \[f(i+k)-f(i) = f(j+k) - f(j) \implies i = j\]

for all i, j, k \in [n].

This is all we need. Here’s code.

import itertools

def is_costas(f):
    n = len(f)
    return all(f[i+k]-f[i] != f[j+k]-f[j]
               for i, j in itertools.combinations(range(n), 2)
               for k in range(1, n-max(i, j)))

I was a bit more judicious instead of checking for every i, j and k like the definition says. There’s symmetry here and I tried to explore it by assigning i and j to elements of 2-combinations.

The definition leaves the restriction of k implicit, we need to make it explicit thus we keep k limited with max(i, j).

And lastly, you need to be careful with the fact that, in contrast with the definition, Python’s indexing is zero-based.

The decision problem of determining if there is at least one permutation of a given length n satisfying the Costas property is sometimes called CAP (Costas Array Problem). I just showed you an O(n3) certificate verification algorithm for this problem, so that means that CAP is in NP.

As far as I know it’s an open question if it’s NP-complete.

You can use this code to search for Costas arrays of a given n by checking permutations. In 6 minutes I could find all Costas arrays up to n=10. Using the same idea in a constraint programming solver I found all Costas arrays up to n=11 in 1 minute.

Computing the Binomial Coefficient

2014.04.22

Looking at the recursive definition looks promising.

    \[ \binom nk = \begin{cases} 1 & k = 0 \text{ or } k = n\\ \binom{n-1}k + \binom{n-1}{k-1} & 0 < k < n \end{cases} \]

It’s easy to code an almost direct version of it.

import functools

def binomial_coefficient(n, k):
    return _bc(n, min(k, n-k))

@functools.lru_cache(maxsize=None)
def _bc(n, k):
    if k in (0, n):
        return 1
    return _bc(n-1, k) + _bc(n-1, k-1)

As an example this image shows all the values that are called to calculate binomial_coefficient(7, 4).

There’s two nontrivial things in this implementation that isn’t in the original definition. First I’m taking advantage of the symmetry:

    \[ \binom nk = \binom n{n-k} \]

So this is why I start computing the binomial coefficient with the second argument being the minimum among k and n-k.

The second thing is that I made _bc a memoized function. For this case python3’s functools.lru_cache decorator works great.

Want more buzzwords? Of course you do. This recursive implementation with the use of memoization characterizes dynamic programming with a top-down approach.

We can push a little further with the symmetry if we just keep using min(k, n-k) at every step.

@functools.lru_cache(maxsize=None)
def binomial_coefficient(n, k):
    min_k = min(k, n-k)
    if min_k == 0:
        return 1
    return (binomial_coefficient(n-1, min_k) + 
            binomial_coefficient(n-1, min_k-1))

Then we won’t need to ever check if k is n. Also no need for a separate _bc function, the idea of having it just to wrap that min was kind of silly anyway.

But hey, we can do considerably better if we change our approach a bit. The problem here is that our recursive formula gives us only a partial order. It’d be nice if we had a total order so that we can have an expression in tail position.

Conveniently the binomial coefficient delivers with this identity:

    \[ \binom nk = \frac{n}{k} \binom {n-1}{k-1} \]

Now let’s revise our definition:

    \[ \binom nk = \begin{cases} 1 & k = 0 \text{ or } k = n\\ \frac{n}{k} \binom {n-1}{k-1} & 0 < k < n \end{cases} \]

The best part is that with this we’ll be able to eliminate a lot of calculations.

Notice that this has nothing to do with top-down versus bottom-up approach. The important thing is that now we can define a tail-recursive function. Or in other words, because we’re coding in python, just a simple accumulator loop will do.

def binomial_coefficient(n, k):
    min_k = min(k, n-k)
    acc = 1
    for i in range(1, min_k+1):
        acc = (acc*(n-i+1))//i
    return acc 

With a little attention to keep the accumulator as an integer, we have in essence implemented the following:

    \[ \binom nk = \prod_{i=1}^k \frac{n-i+1}{i} \]

Which is the way I like best to define the binomial coefficient.