Functores

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

1 Functors

Em Teoria das Categorias Functor é um mapa entre categorias que mapeia objetos e morfismos de uma categoria \(C\) para uma categoria \(D\), ou seja, \(F : C \rightarrow D\) é um functor da categoria \(C\) para a categoria \(D\) se dados objetos e morfismos \(a, b, f \in C\), sendo \(f : a \rightarrow b\) então \(F a, F b, F f \in D\) são objetos e morfismos da cateogria destino e \(F f : F a \rightarrow F b\) é um morfismo dessa categoria. Graficamente temos:

Esse mapa não apenas transforma uma categoria em outra, mas também preserva sua estrutura, ou seja, tanto os morfismos identidades como as composições são mantidas intactas:

\(F id_{a} = id_{F a}\)

e

\(h = g . f \implies F h = F g . F f\)

2 Functors em Linguagem de Programação

Um Functor na categoria \(\mathbf{Hask}\) na verdade é um mapa \(F : \mathbf{Hask} \rightarrow \mathbf{Hask}\), ou seja, um mapa da categoria para ela mesma. Isso também é conhecido como endofunctor.

Na definição acima, podemos perceber que um functor \(F\) pode ser visto como um tipo paramétrico, pois sempre está acompanhado de um tipo \(a\). Dizemos que o tipo \(F\) contém o tipo \(a\), ou seja, ele cumpre o papel de um container.

A ideia de container é familiar em programação, aprendemos tal conceito em estrutura de dados quando somos introduzidos a listas, árvores, mapas. Essas estruturas são paramétricas, não temos simplesmente uma lista, mas sim uma lista de inteiros, uma árvore de strings, um mapa de inteiro para string.

Vamos revisar a definição de uma lista em Haskell:

data List a = Empty | a : (List a)

Uma lista do tipo a pode não conter nada (Empty) ou conter um elemento do tipo a seguido por outra lista (encadeada) do mesmo tipo. Na nossa definição de Functors, \(F = List\). Porém, um Functor é, na verdade, mais do que um container, ele também é um mapa de morfismos. A definição de um Functor em Haskell evidencia essa propriedade:

class Functor F where
    fmap :: (a -> b) -> F a -> F b

que pode ser lida como “Para um tipo \(F\) ser um Functor você deve me fornecer uma função fmap para ele que recebe uma função de a para b e um valor do tipo F a e me devolve um valor do tipo F b.”

Por exemplo, se \(F\) for uma lista, a o tipo Int e b o tipo Char, se você me entregar uma função f :: Int -> Char e uma lista de Int, eu te devolvo uma lista de Char.

Notem porém que em Haskell uma função sempre tem apenas um argumento, a função fmap deve, na verdade, ser lida como:

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

ou seja, a função fmap recebe uma função f :: a -> b e me retorna uma função g :: F a -> F b. Isso é conhecido como lift de uma função em programação funcional. No nosso exemplo, me entregue uma função de f :: Int -> Char e te devolvo uma função g :: [Int] -> [Char]. Um mapa de morfismos! Apesar disso, a primeira interpretação de fmap é mais fácil de ser implementada em Haskell. Vejamos o exemplo para lista:

instance Functor List where
    fmap f []     = []
    fmap f (x:xs) = f x : fmap f xs

Nessa definição passamos como argumentos uma função f e uma lista. Se a lista for vazia, não há nada a ser feito, se a lista contém pelo menos um elemento x (usando o pattern matching x:xs), aplicamos f no elemento x e concatenamos com o resultado da chamada recursiva de fmap no restante da lista:

let xs = 1 : 2 : 3 : []
fmap show xs
-- fmap show (1:xs) = show 1 : fmap show xs
-- = show 1 : fmap show (2:xs)
-- = show 1 : show 2 : fmap show xs
-- = show 1 : show 2 : show 3 : fmap show []
-- = show 1 : show 2 : show 3 : []

O fmap aplica a função f em todos os elementos da lista, transformando um List a em um List b.

3 Tudo é um Functor

Vamos definir diversos Functors existentes no Haskell e, quando pertinente, seu equivalente em outras linguagens. O Functor mais simples que existe é aquele que não armazena nada:

data Const b a = Const b

instance Functor (Const b) where
    fmap _ (Const x) = Const x

Esse Functor projeta os valores do tipo a em um valor constante do tipo b, a função fmap simplesmente ignora a função e continua com o seu valor constante. Apesar de sua definição simples, ele tem diversas utilidades em estrutura de dados mais complexas, além de permitir a construção de Functors de forma automática, conforme veremos mais adiante.

Um outro exemplo de Functor é aquele que guarda um único valor de certo tipo:

data Identity a = Identity a

instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

O Functor Identity a é isomórfico ao tipo a, a função fmap simplesmente aplicar a função f no valor contido dentro do container.

Temos um Functor que descarta informação (Const) e outro que armazena um único elemento de um certo tipo, como definimos um Functor que pode não armazenar nada ou armazenar um único elemento? Podemos construir esse Functor com o tipo soma dos Functors Const e Identity:

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

Esse tipo é isomórfico a um outro tipo definido anteriormente, o tipo Maybe (optional em C++) que, relembrando, é definido como:

data Maybe a = Nothing | Just a

Para verificar que ambos os tipos são isomórficos basta definirmos:

f :: Maybe a -> NadaOuUm a
f Nothing  = Const ()
f (Just x) = Identity x

g :: NadaOuUm a -> Maybe a
g (Left (Const ()))    = Nothing
g (Right (Identity x)) = Just x

f . g = id
g . f = id

Baseado na definição de NadaOuUm, como podemos escrever fmap para o tipo Maybe?

instance Functor Maybe where
    -- fmap _ (Const ()) = Const ()
    fmap _ Nothing = Nothing

    -- fmap f (Identity x) = Identity (f x)
    fmap f (Just x) = Just (f x)

4 Raciocínio Equacional

Precisamos lembrar que apenas definir a função fmap não é suficiente, precisamos verificar se elas obedecem as propriedades de um Functor, ou seja, temos que verificar se:

fmap id = id
fmap (g . f) = fmap g . fmap f

Como em Haskell todas as funções são definidas por igualdade, é possível provar a corretude ou propriedade de certa função utilizando o raciocínio equacional. Vamos verificar se o fmap do tipo Maybe possui as propriedades desejadas:

fmap id Nothing = id Nothing
Nothing = Nothing

fmap id (Just x) = id (Just x)
Just (id x) = Just x
Just x = Just x

fmap (g . f) Nothing = (fmap g . fmap f) Nothing
Nothing = fmap g (fmap f Nothing)
Nothing = fmap g Nothing
Nothing = Nothing

fmap (g . f) (Just x) = (fmap g . fmap f) (Just x)
Just ((g . f) x) = fmap g (fmap f (Just x))
Just (g (f x)) = fmap g (Just (f x))
Just (g (f x)) = Just (g (f x))

5 Functor Writer

Quando aprendemos sobre a categoria Kleisli, vimos o container Writer definido como:

-- data Writer s a = (Identiy a, Const s a)
data Writer s a = (a, s)

Como ficaria a definição de fmap para esse tipo? Agora temos o produto do Functor Identity com o Functor Const:

instance Functor (Writer s) where
    -- fmap f (x, s) = (fmap f x, fmap f s)
    -- (fmap f (Identity x), fmap f (Const s))
    -- Identity (f x), Const s
    fmap f (x, s) = (f x, s)

6 Functor Reader

Um último Functor que será bastante utilizado mais adiante é o Reader, em Haskell ele é definido como:

type Reader r a = r -> a

Ou seja, uma função de r para a. Assim como nos exemplos anteriores, a função fmap age sobre o último parâmetro do nosso tipo, então dada uma função a -> b, precisamos de uma função que transforme um r -> a para um r -> b. Isso é simplesmente a composição de funções!

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

Esse Functor nos diz algo muito importante! Se funções são Functors, funções podem ser interpretadas como containers! Vimos anteriormente que funções puras podem ser memoizadas, ou seja, ter seus resultados pré-computados e armazenados em um container. O inverso também é válido, um container pode ser representado como uma função. E realmente, em Haskell um container é uma função.

O container Maybe Int, por exemplo, é definido pelas funções Nothing que retorna sempre um valor constante e a função Just que recebe um valor x do tipo Int. Com essa intuição, podemos definir tipos infinitos (ex.: stream de dados):

-- lista infinita com os números naturais
nat = [1..]

nat = 1 : fmap (+1) nat
-- 1 : (+1) 1 : (+1) (+1) 1 : ...

7 Composição de Functors

As propriedades de um Functor são importantes para permitir a composição de dois ou mais Functors, isso nos permite definir funções para estruturas mais complexas de forma simplificada:

maybeTail :: [a] -> Maybe [a]
maybeTail [] = Nothing
maybeTail (x:xs) = Just xs

square :: Integer -> Integer
square x = x*x

is :: [Integer]
is = [1 .. 10]

fmap (fmap square) (maybeTail is)
=
(fmap . fmap) square (maybeTail is)

8 Functors em outras linguagens

Em C++ precisamos definir a função fmap com os templates do tipo a e do tipo b. As definições de fmap para o tipo optional e para o tipo vector ficam:

template<class A, class B>
std::optional<B> fmap(std::function<B(A)> f, std::optional<A> opt)
{
    if (!opt.has_value())
        return std::optional<B>{};
    else
        return std::optional<B>{ f(*opt) };
}

template<class A, class B>
std::vector<B> fmap(std::function<B(A)> f, std::vector<A> v)
{
   std::vector<B> w;
   std::transform(std::begin(v), std::end(v), std::back_inserter(w) , f);
   return w;
}

e como exemplo de uso:

int dobra(int x) {
  return 2*x;
}

int main()
{
  std::optional<int> o1, o2;
  std::function<int(int)> f = dobra;

  std::vector<int>  v{ 1, 2, 3, 4 };

  o1 = {3};
  o2 = {};

  std::cout << fmap(f, o1).value_or(-1) << std::endl;
  std::cout << fmap(f, o2).value_or(-1) << std::endl;
  for (auto const& c : fmap(f, v))
    std::cout << c << ' ';
  std::cout << std::endl;

  return 0;
}

Em Python, podemos utilizar o singledispatch, porém temos que inverter a ordem dos parâmetros uma vez que o tipo paramétrico é sempre o primeiro argumento:

from functools import singledispatch

class Maybe:
    def __init__(self, x = None):
        self.val = x

@singledispatch
def fmap(a, f):
    print("Not implemented for" + str(type(a)))

@fmap.register(list)
def _(l, f):
    return list(map(f, l))

@fmap.register(Maybe)
def _(m, f):
    if m.val is None:
        m.val = None
    else:
        m.val = f(m.val)
    return m

f = lambda x: x*2

l = [1,2,3]
m1 = Maybe(2)
m2 = Maybe()

print(fmap(l, f))
print(fmap(m1, f).val)
print(fmap(m2, f).val)

9 Referências

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