Functores Representáveis

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

1 Functors Representáveis

Anteriormente vimos a definição do Functor Reader:

type Reader a b = a -> b

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

O Functor Reader a representa o chamado Hom-Set de uma categoria \(C(a, -)\), ou seja, o conjunto de funções que partem do tipo a. Em Teoria das Categorias, esse mapa entre uma categoria e a categoria \(\mathbf{Set}\) é chamada de representação e o Functor Reader a é chamado de Functor Representável.

Como consequência, todo Functor isomórfico a Reader a também é um Functor Representável. Sendo isomórficos, significa que existem dois morfismos:

alpha :: Reader a x -> F x
beta  :: F x -> Reader a x

alpha . beta = id :: F
beta . alpha = id :: Reader a

Um contra-exemplo de um Functor representável é uma lista! Vamos tentar montar os morfismos alpha, beta para esse Functor partindo de Reader Int. Temos diversas escolhas para alpha, podemos aplicar a função em uma lista arbitrária de Int:

alpha :: Reader Int x -> [x]
alpha h = fmap h [12]

A função inversa poderia ser implementada como:

beta :: [x] -> Reader Int x
beta xs = \y -> head xs

Porém, para o caso de lista vazia essa função não funciona. Não temos outra operação possível que funcione para um tipo x arbitrário.

A definição de um Functor representável em Haskell é dada por:

class Representable f where
  -- a
  type Rep f :: *

  -- alpha :: Reader a x -> F x
  tabulate :: (Rep f -> x) -> f x

  -- beta  :: F x -> Reader a x
  index    :: f x -> Rep f -> x

Nessa definição Rep f é o nosso tipo a em que nosso Functor é representável, o * significa que ele é um tipo não-paramétrico. Substituindo Rep f nas funções, percebemos que tabulate representa nosso alpha e index nosso beta. Vejamos um exemplo de Functor representável com uma lista infinita não-vazia (fluxo contínuo de dados):

data Stream x = Cons x (Stream x)

instance Functor Stream where
  fmap f (Cons x xs) = Cons (f x) (fmap f xs)

A instância Representable fica:

instance Representable Stream where
  type Rep Stream = Integer
  tabulate f = Cons (f 0) (tabulate (f . (+1)))
  index (Cons b bs) n | n == 0    = b
		      | otherwise = index bs (n-1)

A função tabulate cria uma lista infinita do tipo Stream iniciando com f 0 e fazendo, na sequência, f 1, f 2, f 3,.... A função index simplesmente recupera o \(n\)-ésimo elemento dessa lista. Esse Functor é uma generalização da memoização de funções cujo argumento é um inteiro positivo! Vamos verificar a capacidade de memoização da função Fibonacci:

f :: Integer -> Integer
f 0 = 0
f 1 = 1
f n = f (n-1) + f (n-2)

t :: Stream Integer
t = tabulate f

main :: IO ()
main = do
  args <- getArgs
  case args of
    [k] -> do
	      let i = read k
	      print $ f i
	      print $ f i
    [k, "--rep"] -> do
		      let i = read k
		      print $ index t i
		      print $ index t i
    _ -> error "Argumentos inválidos"

Mensurando o tempo de execução desse programa utilizando ou não o Representable Functor, temos:

time ./fib 36
real    0m4.176s

time ./fib 36 --rep
real    0m2.098s

2 Árvore de Jogos

Vamos definir um tipo Functor representável para uma árvore de jogos. Definindo os morfismos tabulate, index para essa estrutura nos permite recuperar prontamente qualquer estado da árvore a partir de uma sequência de jogadas.

Para exemplificar, vamos construir as regras do jogo 8-puzzle, que consiste em um quadriculado de dimensões \(3 \times 3\), contendo um elemento vazio e cujo objetivo é de ordenar os quadriculados na sequência numérica.

A representação de um estado do nosso jogo e as regras de movimentos podem ser definidas com as seguintes estruturas e funções auxiliares:

-- Posso mover o quadrado vazio para qualquer direçao
data Moves = LFT | RGT | UP | DOWN deriving (Show, Enum, Bounded)

-- Estado contendo a coordenada da peça vazia
-- e a matriz da permutação atual
data State = S { zeroX :: Int
	       , zeroY :: Int
	       , board :: [[Int]]
	       } deriving Show

-- | Executa um movimento
move :: Moves -> State -> State
move dir (S x y b) = (S newX newY b')
  where
    b'  = swap val b
    val | inBound newX && inBound newY = (b !! newX) !! newY
	| otherwise                    = 0
    (newX, newY) = addTuple (x, y) (pos dir)

-- Troca um determinado valor pelo zero e vice-versa
swap :: Int -> [[Int]] -> [[Int]]
swap val = map (map change)
  where change sij | sij == val = 0
		   | sij == 0   = val
		   | otherwise  = sij

-- Verifica se a coordenada está dentro do quadrado
inBound :: Int -> Bool
inBound x | x >= 0 && x <= 2 = True
	  | otherwise        = False

-- Função auxiliar para somar coordenadas
addTuple :: Num a => (a, a) -> (a, a) -> (a, a)
addTuple (x1, x2) (y1, y2) = (x1+y1, x2+y2)

-- Mapeia um movimento para o deslocamento de coordenadas
pos :: Moves -> (Int, Int)
pos UP   = (-1,  0)
pos DOWN = ( 1,  0)
pos LFT  = ( 0, -1)
pos RGT  = ( 0,  1)

-- Estado inicial qualquer
initBoard = [[3, 2, 5], [4, 6, 0], [7, 8, 9]]
initState = S 1 2 initBoard

Uma árvore de jogos é definida como uma árvore \(n\)-ária em que cada ramificação representa a execução de uma jogada no estado atual e sua consequência no jogo. Podemos pensar que a árvore de jogos é um Stream de estados que podem ser atingidos através de diferentes ramificações possíveis. Com isso podemos definir a nossa árvore como um nó representando o estado inicial e uma lista de nós representando os próximos possíveis estados:

data GameTree m a = Node a [GameTree m a]

O parâmetro m indica as possíveis jogadas que podem ser feitas no meu jogo, o parâmetro a é o tipo de representação do estado atual. Note que as jogadas devem pertencer a uma lista enumerável e limitada (no Haskell isso é representado pelas classes Enum e Bounded). Podemos então definir nossa árvore como um Functor representável fazendo:

instance (Bounded m, Enum m) => Representable (GameTree m) where
    type Rep (GameTree m) = [m]

    -- :: (Rep Tree -> State) -> Tree State
    -- a lista de filhos da arvore é a aplicação cumulativa de
    -- cada possível movimento
    tabulate f = Node (f []) [tabulate (f . (mv:)) | mv <- [minBound .. maxBound]]

    -- :: Tree State -> Rep Tree -> State
    -- simplesmente percorre as ramificações
    -- seguindo os movimentos executados
    index (Node x ts) []       = x
    index (Node x ts) (mv:mvs) = index (ts !! fromEnum mv) mvs

A função tabulate parte do estado inicial definido pela aplicação da função f na sequência vazia de jogadas. Os nós filhos do nó inicial é a aplicação recursiva de tabulate aplicando a função f na lista composta por uma jogada válida e a lista de jogadas até aquele ponto.

Já a função index simplesmente percorre nossa árvore convertendo cada jogada em um índice, indicando o ramo que deve ser seguido.

A função f que devemos associar ao tabulate é uma função que recebe uma lista de jogadas e retorna o novo estado partindo do estado inicial. Para generalizar vamos fazer essa função, chamada makeMoves, receber um argumento de estado inicial:

-- Dado um estado e uma sequência de movimentos
-- faz cada movimento e chega em um estado novo
makeMoves :: State -> [Moves] -> State
makeMoves s [] = s
makeMoves s (mv:mvs) = makeMoves (move mv s) mvs

Se a lista de jogadas está vazia, ela retorna o próprio estado inicial. Caso contrário, ela retorna sua chamada recursiva alterando o estado inicial para o estado após efetuar a primeira jogada da lista.

Com isso, podemos gerar nossa árvore de jogos utilizando tabulate partindo de um estado inicial:

gameTree = tabulate (makeMoves initState) :: GameTree Moves State

E a função gameState que recebe uma lista de jogadas e retorna o estado gerado se torna simplesmente:

gameState :: (GameTree Moves State) -> [Moves] -> State
gameState t = index t

Essa função pode ser utilizada em um algoritmo de busca em largura, profundidade, Monte Carlo, etc. Note que se quisermos alterar o jogo, basta criar as funções auxiliares das regras específicas. A criação e manipulação da árvore não se altera. O código completo está disponível no repl.it.

3 Referências

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