Limites

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

1 Limites

Podemos agora tentar encontrar a definição de um Produto utilizando os conceitos de Functors e Transformação Natural. Para isso vamos imaginar uma categoria \(C\) com diversos objetos e, então, selecionamos dois objetos \(a, b\). Esses objetos serão utilizados com a base de nosso produto.

Agora, criamos uma nova categoria, denominada \(\mathbf{2}\), que contém apenas \(2\) objetos, denominados \(1, 2\), respectivamente. Junto dessas duas categorias, podemos criar um Functor \(D : 2 \rightarrow C\) que mapeia cada objeto da categoria \(\mathbf{2}\) para os objetos \(a, b\) da categoria \(C\):

Para o próximo passo, selecionamos um objeto \(c \in C\) que representará um candidato para o tipo produto. Tal objeto também tem uma ligação com a categoria \(\mathbf{2}\) através do Functor constante \(\Delta_c\), que mapeia qualquer objeto no objeto \(c\):

Como sabemos que existem apenas dois objetos na categoria \(\mathbf{2}\), é fácil definir transformações naturais entre \(\Delta_c\) e \(D\), podemos definir a transformação \(\alpha, \beta\), em pseudo-Haskell como:

alpha :: Const c x -> D x
alpha (Const c) = D Um -- = a

beta :: Const c x -> D x
beta (Const c) = D Dois -- = b

Podemos nomear essas transformações como \(p, q\), e temos:

Por conta das restrições impostas em uma transformação natural, temos que:

p . deltaC = D Um = a
q . deltaC = D Dois = b

E temos a mesma construção que fizemos originalmente para o produto. Esse tipo de construção é denominada Cone, pois generalizando o padrão formamos uma figura similar a um cone:

A condição necessária para que essa construção seja um Cone é a de que todos os triângulos sejam comutativos.

Definindo \(c\) como o ápice de nosso Cone, queremos encontrar o melhor candidato para o ápice, dentre muitos candidatos. Utilizamos como rankeamento a fatoração \(m\) tal que dado \(c, c’\), \(c\) é melhor que \(c’\) caso exista um único \(m\) que \(p’ = p \circ m\) e \(q’ = q \circ m\). Chamamos o melhor ápice de limite do Functor D, ou \(Lim D\).

A categoria que utilizamos como base da construção é denominada Imagem (\(I\)) e geralmente é deixada implícita nos diagramas.

1.1 Objeto Terminal

Se nossa categoria \(I\) for construída como uma categoria vazia, tudo que resta em nosso Cone é o conjunto de ápices, sendo um deles nosso \(Lim D\):

Nosso limite é definido por um morfismo m :: c -> d que funciona para todos os candidatos c. O único tipo que pode substituir d é o unit () com a função unit _ = ().

2 Equalizadores

Um outro Cone interessante, parte da categoria \(I\) com \(2\) objetos, mas tal que existam dois morfismos f, g :: a -> b:

Esse padrão é conhecido como Equalizador (equalizer) e, por conta da comutatividade, temos que:

q = f. p
q = g .p
f . p = g . p

E podemos interpretar como um sistema de equações:

f :: (Double, Double) -> Double
f x y = 2*y + x

g :: (Double, Double) -> Double
g x y = y - x

p :: Double -> (Double, Double)
p t = (t, -2*t)

O conceito de Equalizer está sendo utilizado na criação dos chamados Refinement Types que permite criar assinaturas de funções com restrições nos tipos:

type Nat = {v:Int | 0 <= v}

fat :: Nat -> Nat
fat 0 = 1
fat 1 = 1
fat n = n * fat (n-1)

Essa construção garante verificar em tempo de compilação se o programa contém alguma aplicação da função fat para elementos negativos do tipo Int, reportando o erro para o usuário. Não é possível fazer esse tipo de construção por padrão no Haskell, porém existe um projeto chamado LiquidHaskell que permite tais construções.

A construção acima do tipo Nat pode ser definida pelos equalizadores f, g:

f :: Int -> Int
f = id

g :: Int -> Int
g = abs

e formado por um tipo [Int] cujo morfismo p é definido como:

p :: [Int] -> Int
p = length

Como a imagem da função p é sempre um número natural, sabemos que nesse domínio f = g. Veremos mais adiante que o tipo lista permite modelar os números naturais através de um Monoid.

3 Pullback

Um outro Cone interessante é conhecido como Pullback e consiste em três objetos \(a, b, c\) que se conectam em um padrão de ligação \(a \rightarrow b \leftarrow c\) que comutam através de um objeto \(Lim D\) da seguinte forma:

Ou seja, temos a igualdade f . p = g . q. Esse padrão define o Tipo Interseção em que os valores são provenientes de dois tipos com um campo em comum. Uma outra aplicação desse padrão é na construção de um SQL JOIN:

data Order = Order { orderId    :: Int
                   , customerId :: Int
                   } deriving Show

data Customer = Customer { customerId' :: Int
                         , country    :: String
                         } deriving Show

orders :: [Order]
orders = [Order 1 1, Order 2 1, Order 3 2]

customers :: [Customer]
customers = [Customer 1 "BR", Customer 2 "US"]

f :: Order -> Int
f = customerId

g :: Customer -> Int
g = customerId'

p = fst
q = snd

db :: [(Order, Customer)]
db = [(o,c) | o <- orders, c <- customers]

pullback s = (f . p) s == (g . q) s

joined = filter pullback db

main = do
  putStr $ unlines $ fmap show joined

Uma outra aplicação é na forma como um compilador lida com herança de classes no paradigma de Orientação a Objetos. A categoria das classes pode ser definida como os objetos sendo as classes e o morfismo \(a \rightarrow b\) implicando que \(a\) herda os métodos de \(b\). Desenhando nosso Cone de cabeça para baixo, temos:

Assumindo que o nó \(D\) é o \(Lim D\) do nosso cone, isso implica que ele contém exatamente os métodos de \(B\) e \(C\), porém sem a duplicação dos métodos de \(A\), ou seja, é a união de \(B\) e \(C\) sem identificação de qual conjunto cada elemento pertence. O objeto \(E\) é uma classe que contém os mesmos métodos de \(D\) e mais alguns novos acrescidos em sua definição.

4 Colimites

Como em todas as construções em Teoria das Categorias, podemos definir a construção complementar ao inverter a direção das setas dos morfismos. Um Colimite é o ápice de um Cocone, ou seja, um Cone com as direções invertidas. Por exemplo, para definir o Coproduto temos:

4.1 Objeto Terminal

Analogamente podemos definir o objeto inicial como o Cocone partindo de uma imagem vazia:

5 Pushout

O complemento do Pullback é conhecido como Pushout e define uma União Disjunta:

Esse tipo de padrão é utilizado no estudo de formação de conceitos durante o aprendizado infantil. A ideia é a de que a criança exposta a figuras rotuladas de forma abstrata infere a classificação de figuras da mesma classe. Por exemplo, imagine que a criança escuta sua mãe chamar um chihuahua e um labrador de cachorro, ao visualizar um pastor alemão ela infere que também é um cachorro dada as similaridades:

Pensando em uma Rede Neural Artificial, podemos pensar nos morfismos atributos_chihuahua e atributos_labrador como duas Redes Convolutivas que extraem as informações de imagens que caracterizam as duas raças conhecidas de cachorros. Da mesma forma, temos os morfismos prob_cachorro_chihuahua e prob_cachorro_labrador como o cálculo das probabilidades de ser um cachorro dadas as carecterísticas extraídas das duas raças.

Isso é um dos padrões estudados para possibilitar a separação do treinamento de redes neurais para diferentes conceitos e, após o aprendizado, fazer a composição das funções de conceito.

6 Referências