Yoneda

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

1 Lema de Yoneda

O Lema de Yoneda diz que:

"Uma transformação natural entre um hom-functor e qualquer outro Functor \\(F\\) é completamente determinado ao especificar o valor do componente inicial do hom-functor."

Para entender esse lema, vejamos duas transformações naturais:

alphaX :: Reader a x -> F x

alphaY :: Reader a y -> F y

Com tais transformações podemos desenhar o seguinte diagrama, que deve ser comutativo:

Como esse quadrado é comutativo, temos que alphaY . Reader a f = (F f) . alphaX. Como um Functor em uma função é a função de alta ordem fmap, temos que: alphaY (fmap f) = fmap f . alphaX, que age sobre uma função h, ou seja, alphaY (fmap f h) = fmap f . alphaX h.

Como o fmap no Functor Reader a é apenas uma composição de funções, temos então que alphaY (f . h) = fmap f . alphaX h. Se fizermos h :: a -> x, temos que alphaY (f . h) é uma transformação natural entre um Reader a a e um F a. Para o caso particular em que x = a e h = id, temos então alphaY f = (F f) (alphaA id). Com isso temos que alphaY f = fmap f (F a), ou seja, temos a definição para nosso alpha:

alpha :: (a -> x) -> F x
alpha h = fmap h fa

Para algum F a. Substituindo h = id, temos:

alpha :: F a
alpha id = fmap id fa = fa

Ou seja, a quantidade de definições de alpha é a mesma que a quantidade de F a, sendo então isomórficas. Podemos prontamente transformar um (a -> x) -> F x em F a fazendo alpha id e um F a em (a -> x) -> F x fazendo fmap h fa, além disso alpha id . (fmap h) = id e (fmap h) . (alpha id) = id.

Se pensarmos no Functor identidade, temos que F = Identity e:

(a -> x) -> x = a

Que pode ser lida como, dada uma função de alta ordem que recebe uma função a -> x e retorna um valor de x, é isomórfica ao tipo a.

Também temos a definição de Co-Yoneda, o complemento do Yoneda, em que:

(x -> a) -> F x = F a

2 Yoneda embedding

Vamos utilizar o lema de Yoneda para criar uma transformação natural entre Reader a e Reader b, ou seja, alpha :: Reader a x -> Reader b x. Pelo lema de Yoneda temos:

(a -> x) -> Reader b x = Reader b a
Reader a x -> Reader b x = Reader b a
(a -> x) -> (b -> x) = (b -> a)

Que nos remete a ideia de Functors contravariantes! Com isso podemos criar duas funções, uma delas que resolve o lado esquerdo da equação:

fromY :: (a -> x) -> b -> x
fromY f b = f (toY b)

Sendo a função toY :: b -> a uma função que converte um tipo b em um tipo a. Podemos recuperar essa função com toY = fromY id.

3 Fmap Fusion

A composição de =fmap=s no Haskell nem sempre é otimizada pelo compilador. Por exemplo, se tivermos o seguinte programa:

data Tree a = Bin a (Tree a) (Tree a) | Nil deriving (Eq, Show)

instance Functor Tree where
  fmap f Nil = Nil
  fmap f (Bin x l r) = Bin (f x) (fmap f l) (fmap f r)

instance Foldable Tree where
  foldMap _ Nil = mempty
  foldMap f (Bin x l r) = f x <> foldMap f l <> foldMap f r


sumTree :: Num a => Tree a -> a
sumTree = getSum . foldMap Sum

t :: Tree Integer
t = go 1
  where go r = Bin r (go (2*r)) (go (2*r + 1))

takeDepth :: Int -> Tree a -> Tree a
takeDepth _ Nil = Nil
takeDepth 0 _   = Nil
takeDepth d (Bin x l r) = Bin x (takeDepth (d-1) l) (takeDepth (d-1) r)

transform :: (Functor f, Num a) =>  f a -> f a
transform = fmap (^2) . fmap (+1) . fmap (*2)

printTree k = print . sumTree . takeDepth k

ao executar printTree k $ transform t, primeiro toda a árvore será percorrida para aplicar o mapa (*2), em seguida toda a árvore é percorrida novamente para aplicar (+1) e mais uma vez para aplicar (^2). Sabemos que, pelas leis do Functor temos que fmap f . fmap g . fmap h = fmap (f.g.h). Podemos automatizar esse processo utilizando o Yoneda Embedding.

Vamos criar o tipo Co-Yoneda CY que representa o lado esquerdo do lema de Yoneda:

data CY f a = forall b . CY (b -> a) (f b)

Precisamos definir uma instância de Functor para esse tipo:

instance Functor (CY f) where
  fmap f (CY b2a fb)  = CY (f . b2a) fb

E, utilizando o que aprendemos sobre Yoneda, podemos definir as funções toCY e fromCY:

toCY :: f a -> CY f a
toCY = CY id

fromCY :: Functor f => CY f a -> f a
fromCY (CY f fa) = fmap f fa

Finalmente, precisamos de uma função que leva uma função f em um contexto de Co-Yoneda e, ao aplicá-la, remove desse contexto:

withCoyo :: Functor f => (CY f a -> CY f b) -> f a -> f b
withCoyo f = fromCY . f . toCY

Agora, se fizermos printTree k $ withCoyo transform t, teremos:

withCoyo transform t = (fromCY . transform . toCY) t
= (fromCY . transform) (CY id t)
= fromCY $ (fmap (^2) . fmap (+1) . fmap (*2)) (CY id t)
= fromCY $ (fmap (^2) . fmap (+1)) (CY ((*2) . id) t)
= fromCY $ (fmap (^2)) (CY ((+1) . (*2) . id) t)
= fromCY (CY ((^2) . (+1) . (*2) . id) t)
= fmap ((^2) . (+1) . (*2) . id) t

Isso é a base da biblioteca Data.List.Stream do Haskell que permite otimizar o uso de funções fmap, filter, fold, dentre outros.

4 Referências

https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ http://hackage.haskell.org/package/stream-fusion-0.1.2.5/docs/Data-List-Stream.html https://alpmestan.com/posts/2017-08-17-coyoneda-fmap-fusion.html