Como implementar sua própria estrutura de dados em Python

() translation by (you can also view the original English article)

A linguagem Python fornece suporte completo para implementar sua própria estrutura de dados usando classes e operadores personalizados. Neste tutorial, você irá implementar uma estrutura personalizada de dados de pipeline que pode executar operações arbitrárias em seus dados. Nós usaremos o Python 3.

A estrutura de dados de pipeline

A estrutura de dados de pipeline é interessante porque é muito flexível. Consiste em uma lista de funções arbitrárias que podem ser aplicadas a uma coleção de objetos e produzir uma lista de resultados. Vou aproveitar a extensibilidade do Python e usar o caractere pipe ("|") para construir o pipeline.

Exemplo ao vivo

Antes de mergulhar em todos os detalhes, vamos ver um simples pipeline em ação:

1	x = range(5) \| Pipeline() \| double \| Ω
2	print(x)
3
4	[0, 2, 4, 6, 8]

O que está acontecendo aqui? Vamos decompô-lo passo a passo. O primeiro elemento range(5) cria uma lista de inteiros [0, 1, 2, 3, 4]. Os inteiros são alimentados por um pipeline vazio designado por Pipeline(). Então uma função "double" é adicionada ao pipeline, e finalmente uma função legal Ω encerra o pipeline e avalia a si mesma.

A avaliação consiste em receber uma entrada e aplicar todas as funções no pipeline (no caso só a função double). Finalmente, podemos armazenar o resultado em uma variável chamada x e imprimir.

Classes Python

O Python suporta classes e tem um modelo orientado a objeto muito sofisticado incluindo herança múltipla, mixins e sobreescrita dinâmica. Uma função __init__() serve como um construtor que cria novas instâncias. Python também suporta um modelo de meta-programação avançado, que não será abordado neste artigo.

Aqui é uma classe simples que tem um construtor __init__() que aceita um argumento opcional x (o padrão é 5) e o armazena em um atributo self.x. Eleatambém tem um método foo() que retorna o atributo self.x multiplicado por 3:

class A:
    def __init__(self, x=5):
        self.x = x

    def foo(self):
        return self.x * 3


Aqui temos um exemplo de como instanciá-lo com e sem um argumento x explícito:

1	>>> a = A(2)
2	>>> print(a.foo())
3	6
4
5	a = A()
6	print(a.foo())
7	15

Operadores personalizados

Com Python, você pode usar operadores personalizados para suas classes para ter uma sintaxe mais agradável. Existem métodos especiais, conhecidos como métodos de "dunder". "Dunder" significa "dois sublinhados" (double underscore). Esses métodos como "__eq__", "__gt__" e "__or__" permitem que você use operadores como "= =", ">" e "|" com suas instâncias de classe (objetos). Vamos ver como eles trabalham com a classe A.

Se você tentar comparar duas instâncias diferentes de A, o resultado será sempre False independentemente do valor de x:

1	>>> print(A() == A())
2	False

Isso ocorre porque o Python compara os endereços de memória de objetos por padrão. Digamos que queremos comparar o valor de x. Podemos adicionar um operador especial "__eq__" que recebe dois argumentos, "self" e "other" e compara seu atributo x:

1	def __eq__(self, other):
2	return self.x == other.x

Vamos verificar:

1	>>> print(A() == A())
2	True
3
4	>>> print(A(4) == A(6))
5	False

Implementando um Pipeline em uma classe Python

Agora que já cobrimos o básico de classes e operadores personalizados em Python, vamos usar isso para implementar nosso pipeline. O construtor __init__() utiliza três argumentos: functions, inputs e terminals. O argumento "functions" é uma ou mais funções. Essas funções são os estágios no pipeline que operam sobre os dados de entrada.

O argumento "input" é a lista de objetos que o pipeline vai operar. Cada item de entrada será processado por todas as funções do pipeline. O argumento "terminals" é uma lista de funções, e quando um deles é encontrado o pipeline avalia e retorna o resultado. Os terminais são por padrão a função input (em Python 3, "print" é uma função).

Observe que, dentro do construtor, um misterioso "Ω" é adicionado aos terminais. Vou explicar isso a seguir.

O construtor do Pipeline

Abaixo a definição de classe e o construtor __init__():

class Pipeline:
    def __init__(self,
                 functions=(),
                 input=(),
                 terminals=(print,)):
        if hasattr(functions, '__call__'):
            self.functions = [functions]
        else:
            self.functions = list(functions)
        self.input = input
        self.terminals = [Ω] + list(terminals)

O Python 3 totalmente oferece suporte a Unicode em nomes identificadores. Isto significa que podemos usar símbolos legais como "Ω" para nomes de variável e de função. Aqui, eu declarei uma função chamada "Ω", que serve como uma função terminal: Ω = lambda x: x

Eu também poderia ter usado a sintaxe tradicional:

1	def Ω(x):
2	return x

Os operadores "or" e "ror"

Aí vem o núcleo da classe Pipeline. Para utilizar o "|" (símbolo pipe), precisamos substituir alguns operadores. O símbolo "|" é usado pelo Python comparação bit a bit ou inteiros. No nosso caso, queremos substitui-lo para implementar um encadeamento de funções, bem como a entrada de alimentação no início do pipeline. Essas são duas operações distintas.

O operador "__ror__" é invocado quando o segundo operando é uma instância de Pipeline, enquanto o primeiro operando não é. Ele considera o primeiro operando como entrada e armazena-o no atributo self.input e retorna a instância de Pipeline (self). Isto permite o encadeamento de funções mais tarde.

1	def __ror__(self, input):
2	self.input = input
3	return self

Aqui está um exemplo onde o operador __ror__() seria invocado: 'hello there' | Pipeline()

O operador "__or__" é invocado quando o primeiro operando for um Pipeline (mesmo se o segundo operando também for um Pipeline). Ele aceita o operando para ser uma função chamada e afirma que o operando "func" de fato pode ser chamado.

Em seguida, ele acrescenta a função para o atributo self.functions e verifica se a função é uma das funções terminal. Se é um terminal então o pipeline inteiro é avaliado e o resultado é retornado. Se não for um terminal, o pipeline em si é retornado.

def __or__(self, func):
    assert(hasattr(func, '__call__'))
	self.functions.append(func)
	if func in self.terminals:
		return self.eval()
	return self

Avaliando o Pipeline

Confome você adiciona cada vez mais funções não-terminal no pipeline, não acontece nada. A verdadeira avaliação é adiada até que o método eval() seja chamado. Isso pode acontecer adicionando uma função terminal no pipeline ou por chamar eval() diretamente.

A avaliação consiste em iterar sobre todas as funções no pipeline (incluindo a função terminal, se houver uma) e executá-las em ordem na saída da função anterior. A primeira função no pipeline recebe um elemento de entrada.

def eval(self):
    result = []
	for x in self.input:
		for f in self.functions:
			x = f(x)
		result.append(x)
	return result

Usando o Pipeline efetivamente

Uma das melhores maneiras de usar um pipeline é aplicar a ele vários conjuntos de entrada. No exemplo a seguir, um pipeline sem entradas e sem funções terminal é definido. Tem duas funções: a infame função double que definimos anteriormente e o padrão math.floor.

Então, nós fornecemos três entradas diferentes. No loop interno, nós adicionamos a função terminal Ω quando podemos invocá-lo para coletar os resultados antes de imprimi-los:

1	p = Pipeline() \| double \| math.floor
2
3	for input in ((0.5, 1.2, 3.1),
4	(11.5, 21.2, -6.7, 34.7),
5	(5, 8, 10.9)):
6	result = input \| p \| Ω
7	print(result)
8
9	[1, 2, 6]
10	[23, 42, -14, 69]
11	[10, 16, 21]

Você poderia usar a função terminal print diretamente, mas em seguida cada item seria impresso em uma linha diferente:

keep_palindromes = lambda x: (p for p in x if p[::-1] == p)
keep_longer_than_3 = lambda x: (p for p in x if len(p) > 3)

p = Pipeline() | keep_palindromes | keep_longer_than_3 | list
(('aba', 'abba', 'abcdef'),) | p | print

['abba']

Futuras melhorias

Há algumas melhorias que podem fazer com que o pipeline seja mais útil:

Adicione streaming para que possa trabalhar em fluxos infinitos de objetos (por exemplo, leitura de arquivos ou eventos de rede).
Fornecer um modo de avaliação onde todo o input é fornecido como um único objeto para evitar uma solução pesada para prover uma coleção de um item.
Adicione várias funções pipeline úteis.

Conclusão

Python é uma linguagem muito expressiva e está bem equipada para projetar sua própria estrutura de dados e tipos personalizados. A capacidade de substituir os operadores padrão é muito poderosa quando a semântica se presta a tal notação. Por exemplo, o símbolo pipe ("|") é muito comum para um pipeline.

Um monte de desenvolvedores Python desfrutam de estruturas internas de dados em Python como tuplas, listas e dicionários. No entanto, projetar e implementar sua própria estrutura de dados pode tornar o sistema mais simples e mais fácil para trabalhar por elevar o nível de abstração e escondendo detalhes internos de usuários. Experimente.