Grupo de Estudos em Haskell da UFABC > Teoria das Categorias > Categorias

Categorias

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

1 Teoria das Categorias

Teoria das Categorias é uma área da Matemática que formaliza, descreve e estuda estruturas abstratas com foco nas relações entre seus objetos.

Uma categoria \(C\) é definida como um conjunto de objetos e morfismos junto com um operador de composição \((\circ)\) que garantem as seguintes propriedades:

Associatividade: \(h \circ (g \circ f) = (h \circ g) \circ f = h \circ g \circ f\).
Identidade: existe uma morfismo identidade partindo de um objeto para ele mesmo de tal forma que \(f \circ id_A = f\) e \(id_B \circ f = f\).
Transitividade: se \(a, b, c \in C\) e \(\exists f : a \rightarrow b, g : b \rightarrow c\), então temos ∃ \(h = g \circ f: a \rightarrow c\).

Os conceitos de composição e poder de abstração são elementos importantes para a criação de programas. A composição permite quebrar problemas em pequenos pedaços para depois juntá-los em uma solução única.

Category theory is the study of compositionality: building big things out of little things, preserving guarantees.It would be utterly astonishing if this were not deeply useful for programming.We have barely scratched the surface of learning how to take advantage of this!

</p>

— kenbot (@KenScambler) 15 de abril de 2019

</blockquote> <script async src="https://platform.twitter.com/widgets.js" charset=“utf-8”></script>

Já a abstração permite o foco na solução de um problema sem nos preocuparmos com detalhes que podem atrapalhar o entendimento do programa principal. A ideia é que primeiro montamos um esqueleto do que queremos implementar para somente depois programar os detalhes. Além disso, com a abstração podemos tornar nosso código genérico o suficiente para ser prontamente aplicado em outros domínios.

‘The purpose of abstraction is not to be vague, but to create a new semantic level in which one can be absolutely precise’ - Edsger Dijkstra pic.twitter.com/S6UruJbBjF

</p>

— Computer Science (@CompSciFact) 4 de janeiro de 2018

</blockquote> <script async src="https://platform.twitter.com/widgets.js" charset=“utf-8”></script>

Como exemplo, considere a seguinte solução para inverter uma string utilizando uma estrutura de pilha:

char * inverte_str(char * orig) {
    int len = 0;
    char * ptr = orig;
    char * dest;
    char * pilha;
    int i, topo = -1;

    while (*ptr != '\0') ++ptr;
    len = ptr - orig;

    dest = malloc(sizeof(char)*(len+1));
    pilha = malloc(sizeof(char)*len);

    for (i=0; i<len; ++i) {
        topo = topo + 1;
        pilha[topo] = orig[i];
    }

    i = 0;
    while (topo != -1) {
        dest[i] = pilha[topo];
        --topo; ++i;
    }
    dest[len] = '\0';

    free(pilha);

    return dest;
}

Mesmo se esse código fosse comentado em cada um de seus blocos, os detalhes de como determinar o tamanho da string, criar e manipular uma pilha complicam o entendimento do programa. Considere agora o mesmo algoritmo utilizando abstrações:

char * inverte_str(char * orig) {
    int len = strlen(orig);
    pilha * p = cria_pilha();
    char * dest;

    dest = cria_str(len);

    while (*orig != '\0') {
        empilha(p, *orig);
        ++orig;
    }

    while (!vazia(p)) {
        *dest = desempilha(p);
        ++dest;
    }

    return dest;
}

Além de tornar o código mais descritivo, passamos a resolver cada um dos problemas relacionados em separado. Primeiro pensamos no programa como um todo, depois pensamos em como criar uma pilha, determinar o tamanho de uma string, etc.

Adicionando o conceito de composição de funções, e supondo a existência das funções:

pilha * empilha_str (pilha *, char *);
char * desempilha_str(pilha *, char *);

podemos tornar nosso programa principal ainda mais declarativo como, por exemplo:

char * inverte_str(char * orig) {
    int len = strlen(orig);
    pilha * p = cria_pilha();
    char * dest;

    dest = cria_str(len);

    return desempilha_str(empilha_str(p, *orig), dest);
}

Os conceitos estudados em Teoria das Categorias têm impulsionado a criação de novas abstrações nas linguagens de programação mais modernas (e nos padrões mais atuais das linguagens tradicionais). Essa tendência é observada com mais clareza nas linguagens de programação funcionais mais modernas como Haskell e Idris, que segue um paradigma puramente funcional, mas também pode ser observada nas linguagens mais populares como C++, Java e Python.

2 Representando uma Categoria

Uma categoria \(C\) e seus objetos e morfismos podem ser apresentados como um grafo em que os nós representam os objetos e as arestas representam morfismos (relacionamentos) entre objetos:

Uma propriedade importante de uma categoria é a de que, se temos um morfismo \(f : a \rightarrow b\) e outro morfismo \(g : b \rightarrow c\), como toda categoria possui um operador de composição, também teremos um morfismo \(g \circ f : a \rightarrow c\).

Representamos como \(C(a, b) = Hom_{C}(a,b)\) os conjuntos de morfismos da categoria \(C\) que partem de \(a\) e chegam em \(b\).

Um exemplo prático de uma categoria é a categoria das páginas Web, em que os objetos são as páginas html e os morfismos são os links entre duas páginas. A função identidade pode ser entendido como a função recarregar página do browser. A composição indica que podemos chegar até uma página \(c\), partindo de \(a\), por intermédio de uma página \(b\).

Um contra exemplo é o relacionamento pessoa X conhece pessoa Y em uma rede social. Embora possamos dizer que X conhece a si mesmo, representando a identidade, não podemos inferir que Se X conhece Y e Y conhece Z, então X conhece Z.

3 Referências

https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://ncatlab.org/nlab/show/category+theory