Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.
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
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.
https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/