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

Exemplos de Categorias

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

1 Categorias Livre

Dado um grafo qualquer, podemos construir uma Categoria Livre (free category). A categoria livre é aquela formada quando temos um grafo inicial e completamos as arestas necessárias para que os objetos e suas relações possuam todas as propriedades necessárias. Esse tipo de construção gratuita é muito utilizado para definir outras estruturas e padrões de interesse.

Como exemplo, considere o seguinte grafo:

Para que esse grafo represente uma categoria precisamos inserir os morfismos identidade:

Finalmente, devemos inserir a composição dos morfismos existentes:

2 Monoid

Um outro exemplo trivial é uma categoria construída a partir de um único objeto com um único morfismo:

A partir desse grafo podemos construir quantos outros morfismos quisermos:

A categoria de apenas um objeto é conhecida como Monoid. Garantindo a identidade nessa categoria podemos também garantir as propriedades de composição, pois todas as arestas começam e terminam no mesmo objeto, então elas podem ser compostas!

Em algebra um Monoid \(M(C, \otimes, \epsilon_{\otimes})\) é definido por um conjunto de valores de um certo objeto \(C\), um operador binário \(\otimes : m \rightarrow m \rightarrow m\), com \(m \in C\) e um valor identidade \(\epsilon_{\otimes}\) correspondente a esse operador, tal que:

\(a, b, c \in C, (a \otimes b) \otimes c = a \otimes (b \otimes c) = a \otimes b \otimes c\)

\(a \otimes \epsilon = \epsilon \otimes a = a\)

Na categoria Monoid, podemos definir um objeto como um morfismo \(f : m \rightarrow m\) implementado por \(\lambda x \rightarrow x \otimes m\) para um certo valor do objeto \(m\).

Por exemplo, vamos pensar nos números inteiros como um Monoid, o operador de multiplicação como o operador binário e o valor \(1\) como o valor identidade. Um possível morfismo pode ser definido como \(f(x) = x*2\), outro como \(g(x) = x*3\), e assim por diante. A identidade é definida por \(id(x) = x*1\). Podemos verificar a composição de morfismos com:

\((g \circ f)(x) = g(f(x)) = g(x*2) = (x*2)*3 = x*2*3\)

Em outras palavras, sendo multN e multM dois morfismos, a composição deles é \(mult[N \otimes M]\).

3 Monoid em Linguagens de Programação

Em Haskell um Monoid é definido como uma classe de tipos:

class Monoid m where
    mempty  :: m
    mappend :: m -> m -> m

Lemos essa definição como: “para um certo tipo m pertencer a classe Monoid, você precisa me fornecer uma função binária mappend e um valor identidade mempty”. Para definir uma instância dessa classe para o produto entre dois números do tipo Int, fazemos:

instance Monoid Int where
    mempty  = 1
    mappend = (*)

Nota: No Haskell a expressão mappend x y = x*y e mappend = (*) representa a mesma coisa, sendo a segunda chamada de point-free ou igualdade extensional, essa expressão fala que a função mappend se comporta exatamente como o operador *. A primeira, também chamada de pointwise equality explicita a operação a ser aplicada nos dois pontos \(x\) e \(y\).

Em C++ a proposta mais atual para definir um Monoid é (no C++20):

template<class T>
  T mempty = delete;

template<class T>
  T mappend(T, T) = delete;

template<class M>
  concept bool Monoid = requires (M m) {
    { mempty<M> } -> M;
    { mappend(m, m); } -> M;
  };

E o exemplo para inteiros com multiplicação é escrito como (testado no compilador g++-8 com flags -fconcepts -std=c++2a):

template<class T>
  T mempty;

template<class T>
  T mappend(T, T);

template<class M>
  concept bool Monoid = requires (M m) {
    { mempty<M> } -> M;
    { mappend(m, m) } -> M;
  };

template<>
int mempty<int> = {1};

int mappend(int x, int y) {
    return x*y;
}

Finalmente, em Python, podemos utilizar o decorator singledispatch para criar funções genéricas (retirada de http://notes.asaleh.net/posts/monoid-pattern-in-python/):

from functools import singledispatch

@singledispatch
def mempty(a):
    raise Error("Not implemented for" + a)

@singledispatch
def mappend(a, b):
    raise Error("Not implemented for" + a)

@mempty.register(int)
def _(a):
    return 1

@mappend.register(int)
def _(a,b):
    return a * b

Uma aplicação prática para a estrutura de Monoids é em processamento paralelo e distribuído. Se precisamos aplicar um operador binário em uma lista de valores durante um processo de fold=/=reduce, podemos dividir essa lista em blocos a serem processados paralelamente. Isso é possível por conta da propriedade de associatividade de um Monoid. Se o Monoid for, também, comutativo, os blocos paralelos não precisam manter a sequência original dos dados.

3.1 Exemplo de aplicação

Vamos imaginar um sistema simples de controle de estoque para uma loja e que, agora, precisamos criar uma função que calcula a somatória de todo seu estoque e outra que zera o estoque de um elemento:

-- Haskell
type Qtd     = Int
type Preco   = Double
data Produto = Produto Qtd Preco
	       deriving (Show)

soma_produtos :: [Produto] -> Produto
soma_produtos ps = foldl somaProdutos (Produto 0 0) ps
  where somaProdutos (Produto q1 p1) (Produto q2 p2) = Produto (q1+q2) (p1+p2)

zera_estoque :: Produto -> Produto
zera_estoque _ = Produto 0 0.0

// C++
typedef struct produto {
    int qtd;
    double preco;
} produto;

produto soma_produtos (produto ps[], int n) {
    produto total = {0, 0.0};

    for (int i = 0; i<n; i++) {
	total.first += ps[i].qtd;
	total.second += ps[i].preco;
    }

    return total;
}

produto zera_estoque (produto p) {
    p.qtd = 0;
    p.preco = 0.0;
    return p;
}

# Python
from collections import namedtuple

Produto = namedtuple('Produto', ['qtd', 'preco'])

def soma_produtos(ps):
    total_q = total_p = 0
    for (q,p) in ps:
	total_q += q
	total_p += p
    return Produto(total_q, total_p)

def zera_estoque(p):
    return Produto(0, 0.0)

Se eu adicionar um novo item no meu tipo produto:

-- Haskell
type Qtd     = Int
type Preco   = Double
type Imposto = Double
data Produto = Produto Qtd Preco Imposto
	       deriving (Show)

// C++
typedef struct produto {
    int qtd;
    double preco;
    double imposto;
} produto;

# Python
Produto = namedtuple('Produto', ['qtd', 'preco', 'imposto'])

terei que adicionar novas instruções em cada uma das funções criadas, o que pode acidentalmente causar bugs em minhas funções. Porém, ao definir as estruturas como um Monoid:

-- Haskell
type Qtd     = Int
type Preco   = Double
data Produto = Produto Qtd Preco
	       deriving (Show)

instance Monoid Produto where
    mempty = Produto 0 0.0
    mappend (Produto q1 p1) (Produto q2 p2) = Produto (q1+q2) (p1+p2)

soma_produtos :: [Produto] -> Produto
soma_produtos ps = foldl mappend mempty ps

zera_estoque :: Produto -> Produto
zera_estoque _ = mempty

// C++
typedef struct produto {
    int qtd;
    double preco;
} produto;

template<>
int mempty<produto> = (produto){0, 0.0};

int mappend(produto x, produto y) {
    produto z = (produto){x.qtd+y.qtd, x.preco+y.preco};
    return z;
}

produto soma_produtos (produto ps[], int n) {
    produto total = mempty<produto>;

    for (int i = 0; i<n; i++) {
	mappend(total, ps[i]);
    }

    return total;
}

produto zera_estoque (produto p) {
    return mempty<produto>;
}

# Python
from collections import namedtuple
from functools import singledispatch, reduce

@singledispatch
def mempty(a):
    raise Error("Not implemented for" + a)

@singledispatch
def mappend(a, b):
    raise Error("Not implemented for" + a)

Produto = namedtuple('Produto', ['qtd', 'preco'])

@mempty.register(Produto)
def _(a):
    return Produto(0, 0.0)

@mappend.register(Produto)
def _(a,b):
    return Produto(a[0] + b[0], a[1] + b[1])

def soma_produtos(ps):
    return reduce(mappend, ps)

def zera_estoque(p):
    return mempty(p)

Não só as funções se tornam mais simples, mas também se tornam genéricas para qualquer estrutura da classe Monoid. Uma alteração em nosso tipo Produto só requer alteração na definição de sua instância da classe:

-- Haskell
instance Monoid Produto where
    mempty = Produto 0 0.0 0.0
    mappend (Produto q1 p1 i1) (Produto q2 p2 i2) = Produto (q1+q2) (p1+p2) (i1+i2)

// C++
template<>
int mempty<produto> = (produto){0, 0.0, 0.0};

int mappend(produto x, produto y) {
    produto z = (produto){x.qtd+y.qtd, x.preco+y.preco, x.impost+y.imposto};
    return z;
}

# Python
@mempty.register(Produto)
def _(a):
    return Produto(0, 0.0, 0.0)

@mappend.register(Produto)
def _(a,b):
    return Produto(a[0] + b[0], a[1] + b[1], a[2] + b[2])

Em Haskell, podemos generalizar as funções criadas acrescentando uma restrição de tipos, especificando que a função deve funcionar para qualquer tipo \(m\) da classe Monoid:

-- Haskell
soma_produtos :: Monoid m => [m] -> m
soma_produtos ps = foldl mappend mempty ps

zera_estoque :: m -> m
zera_estoque _ = mempty

4 Monoid como Tipagem Fraca

Em linguagem de programação, podemos pensar no uso de Monoids para definir tipagem forte e fraca, definindo uma linguagem como tipagem fraca como aquelas que seus tipos formam um Monoid. Ou seja, todos os tipos, mesmo que com nomes diferentes, representam o mesmo objeto. Com isso, todas as funções criadas nessa linguagem podem ser compostas uma com as outras.

5 Ordem

Uma outra categoria interessante é a que define relação de ordem. De forma simples, vamos verificar se a relação de Pré-ordem \((A, \leq)\) define uma categoria. Para todo objeto \(a\) podemos dizer que \(a \leq a\)? Sim! E essa é nossa identidade! Se temos a relação \((a \leq b) \leq c\) podemos também dizer que \(a \leq (b \leq c)\)? Sim, isso confirma nossa associatividade! Finalmente, a composição é definida por:

\((b \leq c) \circ (a \leq b) = a \leq c\)

O que também está correto pela definição de pré-ordem! A categoria da pré-ordem define o mínimo necessário que precisamos ter para definir o conceito de ordem entre objetos. Se adicionarmos outras condições, definimos relações de ordem mais estritas.

A ordem parcial, por exemplo, requer também que se \(a \leq b\) e \(b \leq a\), então \(a\) e \(b\) são os mesmos objetos! Finalmente, na ordem total restringimos ainda mais nossa categoria indicando que quaisquer dois objetos \(a, b\) devem possuir uma relação, seja \(a \leq b\) ou \(b \leq a\). Notem que essas restrições são criadas através de adições (ou remoções) de certas arestas, partindo de uma categoria livre.

6 Referências

https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://ncatlab.org/nlab/show/monoid http://notes.asaleh.net/posts/monoid-pattern-in-python/