Além dos Functores

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

1 Bifunctors

Vimos anteriormente que muitos Functors são aplicados em tipos paramétricos com dois parâmetros. Por exemplo, temos os dois tipos algébricos fundamentais: Either a b e Pair a b. Nesses casos devemos decidir qual parâmetro fica fixo e em qual aplicamos a função. Convencionamos de fixar o primeiro dos tipos paramétricos.

Uma outra construção possível é a de um Bifunctor em que temos um mapa para cada um dos dois tipos parâmetricos e possui definição análoga ao fmap:

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> (f a b -> f c d)

Podemos definir facilmente um Bifunctor para os tipos Either e Pair:

instance Bifunctor Either where
    bimap f _ (Left x)  = Left (f x)
    bimap _ g (Right y) = Right (g y)

instance Bifunctor (,) where
    bimap f g (x, y) = (f x, g y)

Especificamente para o tipo produto, temos em C++ e Python:

template <class A, class B, class C, class D>
pair<C, D> bimap(auto f, auto g, pair<A, B> p){
  return pair<C, D>(f(p.first), g(p.second));
}


template <class A>
auto fmap(auto f, A x) {
    return f(x);
}

string int2str(int x) {
    return "s" + to_string(x);
}

int str2int(string s) {
    return stoi(s,nullptr) + 1;
}

int main() {
    pair<int, string> p;
    p.first = 23;
    p.second = "12";

    pair<string, int> p2 = bimap<int, string, string, int>(int2str, str2int, p);
    cout << fmap(int2str, 23) << endl;
    cout << p2.first << " " << p2.second << endl;

    return 0;
}

def bimap(f, g, t):
    return (f(t[0]), g(t[1]))

print(bimap( str, int, (23, "23") ))
print(bimap( sum, lambda x: x/2, ([1,2,3], 4) ))

Além da função bimap, no Haskell o Bifunctor também é definido através de duas funções first e second com implementações padrão:

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> (f a b -> f c d)
    bimap f g = first f . second g

    first :: (a -> c) -> (f a b -> f c b)
    first f = bimap f id

    second :: (b -> d) -> (f a b -> f a d)
    second g = bimap id g

Com essas definições, o programador pode ou fornecer a função bimap para um tipo paramétrico ou as funções first, second. Para os tipos Either e Pair essas funções ficariam:

instance Bifunctor Either where
    first f (Left x)  = Left (f x)
    first _ (Right y) = Right y

    second _ (Left x)  = Left x
    second g (Right y) = Right (g y)

instance Bifunctor (,) where
    first f (x, y)  = (f x, y)
    second g (x, y) = (x, g y)

2 Composição de Functors e Bifunctors

No post anterior vimos que todos os Functors que definimos até então podem ser criados utilizando os functors Const, Identity, Either, (,). A construção do tipo Maybe, por exemplo, é feito através de:

data Maybe a = Either (Const ()) (Identity a)

Essa construção funciona pois os Functors podem ser compostos, e a instância de Functor para essa definição de Maybe seria:

instance Functor Maybe where
    fmap f (Left x)  = fmap f x
    fmap f (Right y) = fmap f y

Ou seja, definimos o fmap em função de fmap de outros Functors. Uma vez que a construção de um Functor é um processo mecânico, muitas das definições de Functors podem ser derivadas automaticamente pelo compilador. E, realmente, o compilador ghc do Haskell permite que você faça:

{-# LANGUAGE DeriveFunctor #-}

data Maybe a = Nothing | Just a
  deriving Functor

Podemos fazer o mesmo com Bifunctors? Podemos criar um Bifunctor através da composição de dois Functors:

newtype BiComp bf fu gu a b = BiComp (bf (fu a) (gu b))

Nessa construção temos que bf é um Bifunctor (ou construtor de um), fu, gu são Functors e a, b são tipos paramétricos. O que acontece se aplicarmos Bicomp em Either, Const (), Identity, a, b?

Bicomp (Either (Const () a) (Identity b))

Que é uma definição de Maybe b (pois o a é ignorado no Const)! Como definimos a instância de Bifunctor para Bicomp?

instance (Bifunctor bf, Functor fu, Functor gu) =>
  Bifunctor (BiComp bf fu gu) where
    bimap f1 f2 (BiComp x) = BiComp ((bimap (fmap f1) (fmap f2)) x)

3 Functors Covariantes e Contravariantes

Os Functors que vimos até então tem um nome mais específico, eles são chamados de Covariantes. Lembrando do Functor Reader definido como:

type Reader r a = r -> a

instance Functor (Reader r) where
  fmap f g = f . g

Se quiséssemos definir um Bifunctor para o tipo função, teríamos que definir primeiro um Functor para o tipo Op:

type Op r a = a -> r

instance Functor (Op r) where
  fmap :: (a -> b) -> (Op r a) -> (Op r b)
=
  fmap :: (a -> b) -> (a -> r) -> (b -> r)

Não tem como definirmos uma função fmap com essa assinatura! O que precisamos, na verdade, é de um argumento do tipo b -> a. Esse outro tipo de Functor é denominado Contravariante e é formalmente definido como o Functor da categoria oposta (onde as setas são invertidas). Com isso temos:

class Contravariant f where
    contramap :: (b -> a) -> (f a -> f b)

instance Contravariant (Op r) where
    -- (b -> a) -> Op r a -> Op r b
    contramap f g = g . f

4 Exemplo de aplicação: Composição de Comparadores

Imagine que temos as seguintes estruturas de dados:

data Person   = Person   {name :: String
                         , age :: Int
                         }

data Employee = Employee {tag :: Int
                         , person :: Person
                         , salary :: Double
                         }

Dada a função sortBy :: (a -> a -> Ordering) -> [a] -> [a], que recebe uma função que compara dois elementos do tipo a e ordena uma lista de a, podemos definir as seguintes funções de comparação:

cmpAge :: Int -> Int -> Ordering
cmpAge x y | x < y  = LT
           | x > y  = GT
           | x == y = EQ

cmpPerson :: Person -> Person -> Ordering
cmpPerson x y = cmpAge (age x) (age y)

cmpEmployee :: Employee -> Employee -> Ordering
cmpEmployee x y = cmpAge ((age. person) x) ((age.person) y)

Observando essas funções, percebemos um padrão de repetição em nossos códigos. Qualquer novo aninhamento aumentaria a complexidade da nossa função de comparação (imagine um subcampo dentro de uma estrutura JSON ou XML). Idealmente poderíamos ter uma função f que aplica uma função em nossos registros antes de aplicar a função de comparação. Com isso poderíamos fazer algo como:

cmpPerson   = f age cmpAge
cmpEmployee = f (age.person) cmpAge

Qual deve ser a assinatura dessa função?

f :: (?? -> ??) -> (Int -> Int -> Ordering) -> (?? -> ?? -> Ordering)

Vamos generalizar o tipo Int em um tipo genérico a:

f :: (?? -> ??) -> (a -> a -> Ordering) -> (?? -> ?? -> Ordering)

Com isso, o primeiro argumento deve pegar um certo tipo b e transformar em um certo tipo a, pois sabemos ordenar o tipo a:

f :: (b -> a) -> (a -> a -> Ordering) -> (?? -> ?? -> Ordering)

Finalmente, com essa construção, podemos criar uma função que sabe ordenar o tipo b:

f :: (b -> a) -> (a -> a -> Ordering) -> (b -> b -> Ordering)

Digamos que a função de comparação é um Functor do tipo Order a, com isso temos:

f :: (b -> a) -> Order a -> Order b

Já vimos algo parecido com isso…

contramap :: (b -> a) -> F a -> F b

type Order a = a -> a -> Ordering

instance Contravariant Order where
  --contramap :: (b -> a) -> (a -> a -> c) -> (b -> b-> c)
  contramap f c = \x y -> c (f x) (f y)

Com isso nossa ordenação fica:

cmpPerson'   = contramap age cmpAge
cmpEmployee' = contramap (age.person) cmpAge

Note que por conta da forma como um namedtuple é estruturado em Python, esse exemplo se torna tão trivial quanto sorted(es, key=lambda e: e.person.age). Em C++, o código equivalente ficaria:

typedef struct person {
  int age;
  std::string name;
} person;

typedef struct employee {
  int id;
  person p;
} employee;

bool sortAge (int i,int j) { return (i<j); }

int getAge(person p) { return p.age; }
person getPerson(employee e) { return e.p; }

template<class A, class B>
auto contramap(std::function<bool(B, B)> f, std::function<B(A)> g) {
  return [f, g](A x, A y){return f(g(x), g(y));};
}

auto sortEmployee = contramap<employee, int>(sortAge, compose(getPerson, getAge));

5 Profunctors

A classe de um Bifunctor composto de dois Functors e cujo primeiro Functor é Contravariante e o segundo Covariante, é chamada de Profunctor:

class Profunctor p where
  dimap :: (a -> b) -> (c -> d) -> p b c -> p a d
  dimap f g = lmap f . rmap g
  lmap :: (a -> b) -> p b c -> p a c
  lmap f = dimap f id
  rmap :: (b -> c) -> p a b -> p a c
  rmap = dimap id

Dessa forma podemos definir o operador função (->) como um Profunctor (compondo os Functors Op e Reader):

instance Profunctor (->) where
  lmap f g = g . f
  rmap f g = f . g

A definição de Profunctors é utilizada na criação de Lens, que será abordada mais adiante.

6 Referências

https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/