Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.
Imagine que temos diversas funções em C++, como por exemplo:
bool not(bool b) {
return !b;
}
bool is_even(int x) {
return x%2==0;
}
Em determinado momento do projeto, é exigida a criação de um log do traço de execução de cada função no programa. Algo como:
int main () {
not(is_even(2));
not(is_even(3));
}
resultaria no log "even not even not". Quais soluções podemos
propor?
pair<T, string> e
concatenamos o log na função principal:pair<bool, string> not(bool b) {
return make_pair(!b, "not ");
}
pair<bool, string> is_even(int x) {
return make_pair(x%2==0, "even ");
}
int main () {
pair<bool, string> p;
string log = "";
p = is_even(2);
log += p.second;
p = not(p.first);
log += p.second;
p = is_even(3);
log += p.second;
p = not(p.first);
log += p.second;
}
O código fica excessivamente confuso e com muitas chances de bugs difíceis de serem detectados, pois agora não podemos fazer composição de funções. Uma outra solução, mais simples, é o uso de variável global:
string log = "";
bool not(bool b) {
log += "not ";
return !b;
}
bool is_even(int x) {
log += "even ";
return x%2==0;
}
int main () {
not(is_even(2));
not(is_even(3));
}
Nosso código continua simples, as funções mantém sua propriedade de composição, porém elas se tornaram impuras. A consequência é a de que não podemos otimizá-las adequadamente, nem memoizá-las. Além disso, uma pequena mudança ou acesso indevido ao log pode criar bugs.
Podemos encontrar uma solução intermediária entre as duas soluções
propostas? Vamos retomar a primeira solução e criar a função is_odd:
pair<bool, string> is_odd(int x) {
pair<bool, string> p1, p2;
p1 = is_even(x);
p2 = not(p1.first);
return make_pair(p2.first, p1.second + p2.second);
}
Isso é equivalente a composição de duas funções que foram “embelezadas” com um par do tipo de retorno e uma string de log. Bom, se pudermos definir o tipo de retorno como uma categoria ganharíamos de graça a possibilidade de composição de funções!
Vamos definir a categoria Writer da seguinte maneira (em outro tópico
redefiniremos de forma mais genérica):
-- Haskell
type Writer a = (a, String)
// C++
template<class A>
using Writer = pair<A, string>;
# Python
Writer = namedtuple('Writer', ['val', 'log'])
A categoria Writer é um tipo paramétrico que contém um tipo genérico
a e uma String que armazena o traço de execução de nosso programa.
Para ela ser uma categoria, precisamos de um valor identidade, para isso
representaremos como uma tupla de um valor qualquer e a string vazia (no
Haskell vamos chamá-la de return, o motivo será explicado em outro
post):
-- Haskell
return :: a -> Writer a
return x = (x, "")
// C++
template<class A>
Writer<A> identity(A x) {
return make_pair(x, "");
}
# Python
def id_writer(x):
return Writer(x, "")
O motivo de utilizar a String vazia é porque ela é a identidade das
Strings na operação de concatenação (o que isso nos lembra?). A
composição de duas funções na categoria Writer é:
-- Haskell
(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
m1 >=> m2 = \a ->
let (b, s1) = m1 a
(c, s2) = m2 b
in (c, s1 ++ s2)
O operador >=> é conhecido como peixe e, dado um tipo paramétrico
M, ele compõe duas funções do tipo a -> M b e b -> M c, gerando a
função a -> M c e mantendo a estrutura de contâiners M.
// C++
auto const compose = [](auto m1, auto m2) {
return [m1, m2](auto a) {
auto p1 = m1(a);
auto p2 = m2(p1.first);
return make_pair(p2.first, p1.second + p2.second);
};
};
# Python
def compose_writer(m1, m2):
def f(a):
b, s1 = m1(a)
c, s2 = m2(b)
return Writer(c, s1+s2)
return f
Agora nossas funções anteriores podem ser compostas de forma simplificada:
notW :: Bool -> Writer Bool
notW b = (b, "not")
is_even :: Int -> Writer Bool
is_even x = (x `mod` 2 == 0, "even")
is_odd :: Int -> Writer Bool
is_odd = is_even >=> notW
// C++
Writer<bool> notW(bool b) {
return make_pair(!b, "not ");
}
Writer<bool> is_even(int x) {
return make_pair(x%2==0, "even ");
}
Writer<bool> is_odd(int x) {
return compose(is_even, notW)(x);
}
# Python
def notW(b):
return (not b, "not")
def is_even(x):
return (x%2==0, "even")
def is_odd(x):
return compose_writer(is_even, notW)(x)
Essa categoria que acabamos de criar é generalizada pela categoria
Kleisli que é um dos componentes da definição de Monads. Podemos
descrever essa categoria com os objetos sendo os tipos de uma linguagem
de programação e os morfismos de a -> b como sendo funções que recebem
um tipo a e retornam um tipo derivado de b (ex.: Writer b).
Cada um dos tipos derivados devem definir suas regras de composição e
seus valores de identidade. Em particular, descrevemos o monad Writer
que em sua definição completa é mais genérica ainda:
data Writer w a = Writer a w
nessa definição w é a variável de tipo que fixamos em String, mas
ela pode ser qualquer outro tipo!
Considere, por exemplo, a alteração de String para Int e a definição
da função fatorial para esse novo tipo Writer (
código completo ):
type Writer a = (a, Int)
(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
m1 >=> m2 = \x ->
let (y, s1) = m1 x
(z, s2) = m2 y
in (z, s1 + s2)
fatorial :: Int -> Writer Int
fatorial 0 = (1,1)
fatorial 1 = (1,1)
fatorial n = (fatorial >=> (mul n)) (n-1)
mul :: Int -> Int -> Writer Int
mul n x = (n*x, 1)
main = do
print $ fatorial 5
O retorno dessa função será (120, 5). O que ela representa?
Notem que nossa definição de Writer, transformou uma solução que
costuma gerar efeitos colaterais, tornando nossas funções impuras,
em uma função pura.
Relembrando, uma função parcial é aquela que não tem um valor definido
para todos os possíveis argumentos. Como exemplo temos a raíz quadrada e
o recíproco de um número do tipo Double, a primeira função é
indefinida para valores negativos e a segunda para o valor \(0.0\). Para
resolver esse problema, podemos criar um tipo que pode conter um valor
ou pode não conter nada! No Haskell isso é definido pelo tipo Maybe:
data Maybe a = Nothing | Just a
No C++ isso é definido pelo tipo optional:
template<class A> class optional {
bool _isValid;
A _value;
public:
optional() : _isValid(false) {}
optional(A v) : _isValid(true), _value(v) {}
bool isValid() const { return _isValid; }
A value() const { return _value; }
};
Nossas duas funções podem ser definidas como:
-- Haskell
safeRoot :: Double -> Maybe Double
safeRoot x | x < 0 = Nothing
| otherwise = Just (sqrt x)
safeReciprocal:: Double -> Maybe Double
safeReciprocal 0 = Nothing
safeReciprocal x = Just (1.0 / x)
//C++
#include <iostream>
#include <cmath>
#include <tuple>
#include <experimental/optional>
using namespace std;
using namespace experimental;
optional<double> safe_root(double x) {
if (x >= 0) return optional<double>{sqrt(x)};
else return optional<double>{};
}
optional<double> safe_reciprocal(double x) {
if (x != 0) return optional<double>{1.0/x};
else return optional<double>{};
}
# Python
from math import sqrt
def safe_root(x):
if x>=0:
return sqrt(x)
else:
return None
def safe_reciprocal(x):
if x!=0:
return 1.0/x
else:
return None
Como podemos implementar o nosso operador peixe de composição de funções com retorno “embelezados”? Se o retorno da primeira função for o representante de nada, não precisamos continuar a computar o valor, podemos retornar nada imediatamente, evitando erro de execução:
--Haskell
(>=>) :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c)
m1 >=> m2 = \x ->
case m1 x of
Nothing -> Nothing
Just z -> m2 z
//C++
auto const fish = [](auto f, auto g) {
return [f, g](double x) {
auto z = f(x);
if (z) return g(z.value());
else return z;
};
};
# Python
def fish(f, g):
def h(x):
z = f(x)
if z is None:
return z
else:
return g(z)
return h
Com isso, uma sequência de operações que podem falhar, podem ser descritas como:
--Haskell
sequencia = safeReciprocal >=> safeRoot
//C++
auto sequencia = fish(safe_reciprocal, safe_root);
# Python
sequencia = fish(safe_root, safe_reciprocal)
https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/