Funções

Função é o conceito que atravessa toda a matemática e toda a computação. A definição matemática é mais restrita do que "função" em programação, e a diferença é justamente o que explica vários comportamentos do dia a dia.

Definição

Uma função $f: A \to B$ associa a cada elemento de $A$ exatamente um elemento de $B$. O conjunto $A$ é o domínio, $B$ é o contradomínio, e

$$\operatorname{Im}(f) = {f(a) : a \in A} \subseteq B$$

é a imagem.

Duas exigências merecem destaque, porque é onde a noção matemática difere da computacional:

1. Totalidade — todo elemento do domínio tem imagem. Uma "função" que lança exceção para certas entradas é, matematicamente, uma função parcial.
2. Determinismo — a mesma entrada sempre produz a mesma saída. random() e now() não são funções nesse sentido.

Programação funcional chama de pura exatamente a função que satisfaz as duas condições. É por isso que funções puras podem ser memoizadas, reordenadas e paralelizadas com segurança, e impuras não.

Injetividade, sobrejetividade, bijeção

Propriedade	Definição	Significado
Injetora	$f(a_1) = f(a_2) \to a_1 = a_2$	Não colide: entradas distintas, saídas distintas
Sobrejetora	$\forall b \in B, \exists a, f(a) = b$	Cobre todo o contradomínio
Bijetora	Injetora e sobrejetora	Correspondência perfeita

Só funções bijetoras têm inversa $f^{-1}: B \to A$ com $f^{-1}(f(a)) = a$.

Um resultado de contagem que decorre diretamente: se $|A| > |B|$, nenhuma função $A \to B$ pode ser injetora. Este é o princípio da casa dos pombos, e é o que garante que toda função de hash colide quando o espaço de entrada é maior que o de saída.

Composição

$$(g \circ f)(x) = g(f(x))$$

A composição é associativa mas não comutativa. Ela preserva as propriedades acima: composição de injetoras é injetora, de sobrejetoras é sobrejetora, de bijeções é bijeção.

Em código, composição é o encadeamento de transformações — map(g, map(f, xs)) equivale a map(g ∘ f, xs), e é essa igualdade que permite a um compilador ou a uma biblioteca de streams fundir dois laços num só.

Exemplo trabalhado

Classificar $f: \mathbb{Z} \to \mathbb{Z}$, $f(x) = 2x$.

• Injetora? Sim: $2a = 2b$ implica $a = b$.
• Sobrejetora? Não: nenhum inteiro tem imagem $3$.
• Logo não é bijetora e não tem inversa em $\mathbb{Z}$.

Agora mude o contradomínio para o conjunto dos pares. A mesma regra passa a ser bijeção, com inversa $x \mapsto x/2$.

A lição é importante: injetividade e sobrejetividade dependem dos conjuntos escolhidos, não só da fórmula. É o mesmo motivo pelo qual mudar o tipo de retorno de uma função muda o que se pode garantir sobre ela.

Funções em computação

Hashing. $h: U \to {0, \dots, m-1}$ com $|U| \gg m$. Nunca injetora, logo colisões são inevitáveis e toda tabela hash precisa de estratégia de resolução. Uma boa função de hash distribui a imagem uniformemente; ela não evita colisões, apenas as espalha.

Criptografia. Uma função de mão única é fácil de calcular e difícil de inverter, mesmo sendo matematicamente inversível. Já uma cifra é uma bijeção — do contrário decifrar seria ambíguo. Funções de resumo criptográfico não são bijeções, e é aí que entra a resistência a colisões.

Índices de banco. Um índice único impõe injetividade sobre a coluna. Uma chave estrangeira impõe que a imagem esteja contida no conjunto de chaves da tabela referenciada.

Sistemas de tipos. A assinatura A -> B é literalmente uma função. Currificação é a bijeção entre $C^{A \times B}$ e $(C^B)^A$ — isto é, entre funções de dois argumentos e funções que devolvem funções.

Memoização. Só é correta para funções puras. Guardar resultado de uma função que depende de estado externo produz respostas obsoletas.

Funções parciais e o tipo opcional

Divisão não é função total em $\mathbb{R}$: não está definida em zero. Linguagens tratam isso de três formas — exceção, valor sentinela ou tipo opcional (Option, Maybe, Result).

O tipo opcional é a solução que restaura a totalidade: em vez de $f: A \to B$ parcial, define-se $f: A \to B \cup {\text{nada}}$, que é total. Por isso o compilador consegue exigir que o caso ausente seja tratado — a informação passou a estar no tipo.

Cardinalidade e contagem

Para conjuntos finitos, o número de funções $A \to B$ é $|B|^{|A|}$ — daí a notação $B^A$. Cada elemento do domínio escolhe independentemente sua imagem.

O número de funções injetoras de um conjunto de tamanho $k$ num de tamanho $n$ é $n(n-1)\cdots(n-k+1)$, que é zero quando $k > n$ — reencontrando a casa dos pombos.

Erros comuns

• Confundir contradomínio com imagem. Sobrejetividade é justamente a afirmação de que os dois coincidem.
• Chamar de função algo não determinístico. Isso invalida memoização e otimizações do compilador.
• Supor que uma função injetora tem inversa sem verificar a sobrejetividade.
• Esperar que hashing seja injetor. Comparar apenas hashes para decidir igualdade é um defeito, não uma otimização.

Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill. ISBN 9781259676512. Paul R. Halmos (1974). Naive Set Theory. Springer. DOI: 10.1007/978-1-4757-1645-0.

Referências

1. Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill.
2. Paul R. Halmos (1974). Naive Set Theory. Springer.