Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.
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.
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.
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
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))
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).
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.
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.
https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/