Há algumas semanas atrás eu fiz um curso de Teoria das Categorias na UFABC, e apesar disso não me fazer especialista no assunto, decidi que criaria esse artigo para tentar passar o que eu aprendi. Principalmente por sentir que existe muito misticismo no assunto para quem não conhece.
Mas afinal, o que é Teoria das Categorias?
É um tema originado na matemática que tem como base objetos e morfismos.
Não se assuste, a imagem é mais simples do que imagina!
Olhando para a ela, os objetos são X, Y e Z. E os morfismos, são aquilo que transforma um objeto em outro, ou seja, f e g (as setas). Como temos algo que transforma de X para Y e outro de Y para Z, podemos ter um morfismo que faz as duas operações! Em matemática isso é expressado com ∘, no nosso cenário é g ∘ f.
E sim o operador ∘ é da direita para esquerda, ou seja, o f seria aplicado, para então o g ser aplicado em seu resultado.
Teoricamente é possível aplicar a Teoria das Categorias para quase qualquer coisa. Por algum motivo, alguém um dia decidiu relacionar isso com programação. É possível fazer a relação entre os dois assuntos de várias formas, a mais comum é mapear objetos para tipos e morfismos para funções.
Como os objetos, no nosso caso tipos em programação, são fundamentais para falar da teoria das categorias, irei mostrar os exemplos em uma linguagem estaticamente tipada que considero acessível, TypeScript.
Um exemplo em código da imagem anterior seria:
class X {}
class Y {}
class Z {}
function f (x: X): Y {
...
}
function g (y: Y): Z {
...
}
function fComposedWithG(x: X): Z {
const y = f(x)
return g(y)
}
// fComposedWithG também pode ser escrito como:
function fComposedWithG(x: X): Z {
return g(f(x))
}Ta, então uma categoria é um conjunto de objetos e morfismos?
Quase isso.
Para ser uma categoria, além de mapear os objetos e morfismos, é necessário também cumprir algumas regras na composição (∘), são elas:
- Associatividade;
- Identidade.
A associatividade tem a ver com poder agrupar as operações em qualquer ordem, garantindo que terão o mesmo resultado.
class A {}
class B {}
class C {}
class D {}
function f (a: A): B {
...
}
function h (b: B): C {
...
}
function g (c: C): D {
...
}
// h ∘ (g ∘ f) == (h ∘ g) ∘ f == h ∘ g ∘ f
//
// Não importa a ordem dos agrupamentos, no final
// a composição terá o mesmo resultado.Já a identidade é sobre ter um morfismo que leva de um objeto a ele mesmo, de forma que se for composto a outro morfismo que começa ou termina nesse objeto, acaba no mesmo resultado.
function identity<T>(t: T): T {
return t
}
// identity ∘ f == f
// f ∘ identity == f
//
// Ou seja, uma função `f` composta com a
// identidade sempre da o mesmo resultado,
// independente da ordem da aplicaçãoAgora que temos uma definição (ou quase isso), vou mostrar algumas das categorias mais conhecidas e faladas, e tentar desmistificar elas.
A primeira categoria que as pessoas costumam aprender é Monoid. A primeira coisa que é possível induzir pelo nome é a palavra mono, que vem de um.
Esse um se trata dela conter apenas um objeto.
Para ser um Monoid é preciso ter as seguintes duas propriedades:
- Um operador binário. Ex: um morfismo que recebe dois parâmetros e retorna um;
- Um elemento neutro.
Mapeando esses conceitos para programação, podemos considerar que categorias podem ser encararadas como interfaces. Se você não conhece o conceito de interfaces, eu aconselho entender isso antes, caso não tenha mexido ainda em uma linguagem estaticamente tipada.
Segue abaixo a definição escrita acima, na forma de código:
interface Monoid<M> {
mappend(x: M): M // operação binária
mempty(): M // elemento neutro
}Você pode não saber, mas já conhece exemplos de Monoid. Um deles é a soma de números inteiros. Pare para pensar, o que caracteriza uma soma?
- Dois lados, os quais serão unidos para gerar um número;
- Um número base que pode ser somado "n" vezes a ele mesmo e/ou a outros números, que sempre gera o mesmo resultado (5 + 0 + 0 = 5).
Consegue ver como essas duas características podem ser interpretadas como uma Monoid?
Exemplo:
Number.prototype.mappend = function (x: Number): Number {
return this + x
}
Number.prototype.mempty = function (): Number {
return 0
}
console.log('mappend:', Number(5).mappend(4)) // 9
console.log('mempty:', Number().mempty()) // 0O exemplo acima não implementa exatamente a interface no
TypeScript, fiz dessa forma pois achei mais simples. Criei outro exemplo que cria um novo tipoNumberpara implementar a interface Monoid caso queira ver: Link para o código.
Uma outra operação que podemos encaixar no conceito de Monoid é a multiplicação de números inteiros.
Number.prototype.mappend = function (x: Number): Number {
return this * x
}
Number.prototype.mempty = function (): Number {
return 1
}
console.log('mappend:', Number(5).mappend(4)) // 20
console.log('mempty:', Number().mempty()) // 1A diferença é que para a multiplicação, o número neutro é 1, visto que 5 * 1 * 1 é igual a 5.
Existem dois outros exemplos de Monoid que você conhece e talvez não tenha percebido!
São eles Strings e Arrays.
String.prototype.mappend = function (x: String): String {
return this + x
}
String.prototype.mempty = function (): String {
return ""
}
console.log(
'String mappend:',
String("category").mappend(" ").mappend("theory")
) // "category theory"
console.log('String mempty:', String().mempty()) // ""
Array.prototype.mappend = function (x: Array): Array {
return this.concat(x)
}
Array.prototype.mempty = function (): Array {
return []
}
console.log('Array mappend:', Array(1, 2).mappend([3])) // [1, 2, 3]
console.log('Array mempty:', Array().mempty()) // []Uma nota que gostaria de dizer é que a função
memptyteoricamente deveria ser implementada como um método estático, pois tem mais a ver com o tipo do que com uma instância do tipo. Isso não foi feito pois interfaces emTypeScriptnão podem ter métodos estáticos, achei mais claro agrupar tudo em uma interface só.
Um Functor é uma categoria que mapeia os objetos e morfismos de uma categoria, para outra.
Se formos pensar na categoria dos tipos, ou seja, mapear objetos para tipos e morfismos para funções, teriamos na verdade Endofunctors, que mapeiam da categoria dos tipos para ela mesma.
Ou seja, uma categoria dos tipos teria todos os tipos de uma linguagem, exemplo: Number, String, Array, etc, e um Functor transformaria um valor de um tipo para outro, ou para um valor do mesmo tipo, pois todos estão dentro da mesma categoria, a dos tipos!
Tenha calma, todas essas palavras ficarão mais claras com os exemplos. E você provavelmente já conhece um exemplo de Functor.
A interface de um Functor seria algo como isso:
interface Functor<A> {
fmap<B>(f: (a: A) => B): Functor<B>
}Ou seja, ele define uma função para um Functor do tipo A o qual recebe uma função f que mapeia um valor do tipo A, para um valor do tipo B, e de retorno o fmap entrega um Functor do tipo B.
Que confusão de tipos!!
Vamos pensar em um cenário simples, imagine o tipo abaixo:
class Container<T> {
private value: T
constructor(value: T) {
this.value = value
}
}
console.log('simple container:', new Container(5)) // Container { value: 5 }O que temos aqui é uma classe simples que guarda um valor de qualquer tipo na sua construção.
Vamos supor que temos um Container que guarda um inteiro, e queremos o converter pra string, mantendo o valor no Container. Uma forma de fazer isso é implementando Functor para nosso tipo!
class Container<T> implements Functor<T> {
private value: T
constructor(value: T) {
this.value = value
}
fmap<U>(f: (a: T) => U): Functor<U> {
return new Container(f(this.value))
}
}
console.log(
'map integer container to string container:',
new Container(5).fmap((a) => String(a))
) // Container { value: "5" }Inclusive, uma melhoria no código acima poderia ser só passar a função
Stringcomo parâmetro ((a) => String(a)vsString), mas fiz da forma acima para ficar mais explícito o que acontece.
Um container que você já conhece hoje que tem a função fmap é o Array do JavaScript, só não tem o prefixo f no nome!
console.log('mapped list:', [1, 2, 3].map(x => x * 2)) // [2, 4, 6]No caso o map aplica a função passada por parâmetro em todos os seus itens, gerando uma nova lista de mesmo tamanho, com os novos valores.
Como pode ver o Functor mapeia algo de um tipo a outro o mantendo sua estrutura de dados, independente de criar uma nova ou não.
Aquela que todos que a entendem tem pós graduação em ciências da computação!
A Monad tem conceitos similares as duas outras categorias acima. Vamos defini-la:
- Possui uma operação similar ao
fmap, mas ao invés de mapear algo do tipoApara o tipoB, ela mapeia o tipoA, para uma Monad do tipoB; - Uma operação, que constrói uma Monad a partir de um valor.
Em código seria algo como:
interface Monad<A> {
bind<B>(f: (a: A) => Monad<B>): Monad<B>
return(a: A): Monad<A>
}Na verdade, existe mais de uma implementação de Monad, mas utilizei a acima pois é a mais utilizada hoje em dia.
Implementando usando nosso tipo Container:
class Container<T> implements Monad<T> {
private value: T
constructor(value: T) {
this.value = value
}
bind<U>(f: (a: T) => Monad<U>): Monad<U> {
return f(this.value)
}
return(a: T): Monad<T> {
return new Container(a)
}
}
console.log(
'bind container with 5 to container with 15:',
new Container(5).bind((a) => Container(a + 10))
) // Container { value: 15 }
console.log(
'return:',
new Container(undefined).return(6)
) // Container { value: 6 }Assim como comentei que o método
memptyde Monoid mapearia melhor se fosse um método estático, oreturnde Monad também. Digo isso pois não precisam do objeto inicial, apenas dos argumentos.
Assim como o fmap, também temos o bind no JavaScript, e seu nome é flatMap!
console.log('flatten list:', [1, 2, 3].flatMap(x => [x * 2])) // [2, 4, 6]O
flatMapnão chega a ser exatamente igual aobind, mas possui suas similaridades.
Já o return, com um nome infeliz nas linguagens C-like, lembra mais a ideia de um construtor, que pega um valor qualquer e transforma no Container.
Teoria das Categorias é um assunto extenso, e possui uma profundiade e complexidade muito maior do que o que mostrei aqui. Caso tenha interesse em entender mais do assunto, recomendo o livro Category Theory for Programmers.
Espero ter clareado um pouco mais o que é Teoria das Categorias e o que é cada uma das 3 categorias que apresentei, e se possível ter despertado mais curiosidade no assunto em você.