Tipos e Funções

Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.

1 Categoria dos Conjuntos

A categoria dos conjuntos, denominada de Set, é a categoria cujos objetos são conjuntos e os morfismos são funções totais entre dois conjuntos. Ela é um exemplo trivial de categoria e muito utilizada para estudos de categorias.

Uma função total é toda função \(f : X \rightarrow Y\) em que todos os elementos \(x \in X\) possui um correspondente \(f(x) \in Y\). Como contraste, uma função parcial é toda função \(f : X \rightarrow Y\) em que existe pelo menos um elemento \(x \in X\) que não possui correspondente \(f(x) \in Y\). Uma função parcial é uma função total em um subconjunto \(X' \subset X\).

Uma vez que todo conjunto \(X\) possui uma função identidade e o conceito de composição entre funções está formalizado em teoria dos conjuntos, a categoria Set atende a todas as propriedades necessárias para uma categoria. Durante as próximas postagem serão destacadas diversas correspondências entre a categoria dos conjuntos e a categoria dos tipos, usada em programação.

2 Categoria dos Tipos

Em linguagem de programação, um tipo representa um conjunto de valores. Por exemplo, um tipo booleano, chamado Bool, é o conjunto contendo os valores \(\{True, False\}\), o tipo Int corresponde aos valores inteiros, geralmente representáveis com \(32\) bits. Na categoria dos tipos os objetos são os tipos e os morfismos são funções mapeando um tipo para outro (ou ele mesmo).

A assinatura de uma função representa a origem e destino de um morfismo, em nosso contexto, o tipo de entrada e tipo de saída da função. Utilizaremos a notação da linguagem Haskell que é similar a notação matemática para conjuntos:

-- função f que recebe um Int e retorna um Bool
f :: Int -> Bool

que, em linguagens que adotam C-style, é equivalente a:

bool f (int);

Funções de duas variáveis em Haskell são representadas como:

f :: Int -> Char -> Bool

que representa uma função que recebe um inteiro e um caractere e retorna um booleano. Na verdade, essa função é uma função de uma varíavel (Int) que retorna uma função Char -> Bool. Veremos mais adiante que ambas interpretações são equivalentes.

2.1 Identidade

Para que os tipos formem uma categoria, precisamos verificar as suas propriedades. A primeira propriedade é a existência de uma função identidade. Conseguimos criar uma função identidade que funciona para todo e qualquer tipo da linguagem?

Em Haskell, essa função seria:

id :: a -> a
id x = x

A variável a na assinatura da função é um tipo polimórfico, lemos essa assinatura como /definimos uma função que funciona para todo tipo a, tal que ele recebe um valor desse tipo e retorna um valor do mesmo tipo/. Em C++, essa função deve fazer uso de template:

template <class A>
A id(A x) return x;

E em Python, graças a tipagem dinâmica, escrevemos simplesmente:

def id(x):
    return x

2.2 Composição

Agora precisamos definir uma função que faz a composição entre duas funções. A linguagem Haskell já possui o operador . que faz esse papel:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
g . f = \x -> g (f x)

A assinatura da função indica que recebemos como parâmetros uma função do tipo b para o tipo c, uma do tipo a para o tipo b e retornamos uma função do tipo a para o tipo c. O operador cria uma função anônima (\(\lambda\)) que recebe um valor \(x\) do tipo a, aplica f em x e, em seguida, aplica g no resultado anterior.

Em C++11 podemos fazer uma implementação similar utilizando funções anônimas:

auto const compose = [](auto f, auto g) {
	return [f, g](auto x) {
		return g(f(x));
	};
};

Em Python, esse mesmo código fica:

def compose(f, g):
    return lambda x: g(f(x))

2.3 Garantindo funções totais

Os morfismos da categoria dos tipos, diferente da categoria dos conjuntos, podem não terminar (halting problem), por conta disso todo tipo em Haskell contém um valor chamado bottom (\(\bot\)), isso garante que todas as funções se tornem totais! Suponha uma função f :: Bool -> Int definda como:

f :: Bool -> Bool
f True = 1

A ausência de uma definição da função para a entrada False automaticamente define:

-- undefined é a palavra-chave para bottom
f False = undefined

Chamar a função f passando o valor False, leva a um erro de execução por não ter tal relação definida. O bottom pode também representar funções que nunca terminam (ex.: laços infinitos). A categoria dos tipos do Haskell é chamada de Hask (embora ela não seja estritamente uma categoria).

3 Funções Puras

Uma outra definição importante é a de função pura, ou seja, toda função que não possui efeitos colaterais. Em outras palavras, toda vez que a função \(f\) for executada com o mesmo argumento \(x\) ela deve sempre retornar o mesmo valor \(y\). Um exemplo de função pura em Python é:

def dobra(x):
    return 2*x

e um exemplo de função impura:

def multRand(x):
    return random()*x

Um outro exemplo são funções que fazem leitura e alteração de entrada e saída de dados (ex.: arquivos, stdin=/=stdout, banco de dados). Considere a seguinte função:

def escreve(s):
    with open("arq.txt","a") as f:
	f.write(s)
    with open("arq.txt","r") as f:
	lines = f.readlines()
    return lines

Ao executarmos duas vezes com a entrada “ola”, recebemos como resposta:

escreve('ola')
> ['ola']
escreve('ola')
> ['olaola']

Podemos pensar em uma função pura como toda aquela que pode ser memoizada ou inserida em um tipo Map.

4 Tipos e Funções fundamentais

O Haskell possui dois tipos fundamentais que servem como base para a criação de todos os outros: Void e ():

data Void

data () = ()

O tipo Void é um tipo que não contém elementos, ele representa um tipo de cardinalidade \(0\). Já o tipo (), também conhecido como Unit, é um tipo que contém apenas um valor (ele mesmo), esse tipo é equivalente ao void do C/C++/Java e do None do Python.

Quantas funções podemos construir com assinatura Void -> a? Apenas uma:

absurd :: Void -> a

Essa função não possui implementação, pois não pode ser executada! Ela é equivalente a lei da lógica clássica ex falso quodlibet que diz que qualquer coisa pode seguir de uma contradição.

E quantas funções existem com uma entrada qualquer e o tipo de saída ()?

unit :: a -> ()
unit x = ()

Uma função que retorna um unit mapeia todos os elementos do tipo a para um valor único! Por outro lado, uma função:

x :: () -> Int
x () = 10

Funciona como um seletor de valores de um tipo, sendo equivalente a definição de uma variável:

x :: Int
x = 10

Isso pode ser traduzido para C++ da seguinte forma:

// T -> ()
template <class T>
void unit(T x) {
    // efetua processamentos, geralmente com efeitos colaterais
    return;
}

// () -> int
int x(void) return 10;

Em Haskell o tipo Bool contém apenas dois valores e é definido como:

data Bool = True | False

Podemos pensar em uma função f :: a -> Bool como um predicado. Exemplos:

isAlpha :: Char -> Bool
isGreaterThanFive :: Int -> Bool

Quantas funções diferentes podemos criar com a assinatura Bool -> Bool? Veremos mais adiante a resposta e a relação de funções com tipos.

5 Referências

https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/