Retrospectiva 2011

Dezembro 31, 2011

Agora que estamos no final do ano, vou fazer uma retrospectiva dos principais acontecimentos de 2011.

Primeiro Semestre

O primeiro semestre foi bastante cansativo, mas também produtivo.

Artigos. Escrever artigos é uma das coisas que mais me motivam do meio acadêmico. Desde o final de 2010 estávamos escrevendo um artigo que acabou sendo aceito em uma conferência chamada CGA (Computational Geometry Applications). Logo no começo do ano, um resumo estendido nosso foi aceito no CTW (Cologne-Twente Workshop). Quando comecei a escrever minha dissertação, enxergamos a possibilidade de escrever ainda outro artigo, que foi aceito no Sibigrapi. Mais detalhes aqui.

Google Summer of Code. Durante o primeiro semestre, fui aceito no Google Summer of Code, para trabalhar com um projeto de computação gráfica. Tive que conciliar esse projeto com a escrita da minha dissertação e a escrita para o Sibgrapi! Felizmente, no final deu tudo certo. Escrevi vários posts sobre esse projeto.

Google Code Jam. Não consegui me classificar para a penúltima fase, mas acabei ficando entre os 1000 classificados e ganhando uma camiseta :)

Sibgrapi. Fui apresentar nosso artigo aceito para o Sibgrapi em Maceió. Foi meu primeiro congresso e a primeira vez que apresentei em inglês e para um público grande. Escrevi um post contando mais sobre o evento.

Defesa do mestrado. Depois de aproximadamente 2 anos de trabalho árduo conclui meu projeto de mestrado com a defesa da minha tese.

Emprego em otimização. Graças à indicação do Carlos, estou trabalhando em uma empresa de otimização. Até o momento estou aprendendo bastante sobre desenvolvimento de software em Java, além de ler artigos e implementar soluções para problemas de escalonamento.

Segundo Semestre

No restante do segundo semestre as coisas foram bem mais calmas.

Codefest. Participamos de uma competição onde deveríamos atacar um problema de otimização, tendo duas semanas para implementar uma solução. No final deixamos de levar o prêmio devido a uma bobeira, conforme descrevi aqui.

Haskell. Decidi começar a aprender Haskell com o objetivo de melhorar minhas habilidades de programação. Tenho me surpreendido com a elegância de alguns trechos de código que tenho visto e com a própria sintaxe da linguagem.

Blog

O blog está prestes a completar 3 anos e contando com esse post, são 97 no total. Tenho conseguido manter minha resolução de postar uma vez por semana.

Os posts mais acessados este ano foram: Algoritmo de Branch and Cut, Ponto dentro de polígono e Dijkstra e o caminho máximo.

Os termos mais utilizados em engines de busca foram: “soccer“, “aisec” e “ray tracing“. Um termo de busca curioso é “obter o poligono simetrico cgal“, que apareceu 89 vezes e eu nem faço ideia do que seja isso!

O blog teve, em média, 42 visitas por dia, com um total de 16k desde o seu início. O dia com mais visitas foi 30 de Novembro com 104 visitantes.

Resoluções para 2012

Para 2012, já me matriculei em dois cursos online de Stanford: Probabilist Graphical Models e Natural Language Processing.

Eu gostaria de aprender mais sobre mineração de dados (data mining) voltado ao suporte de tomada de decisões e também sobre otimização/programação estocástica, que considera fatores de incerteza, muito presentes nos problemas que atacamos na indústria. Dado isso, acho que o curso de modelos gráficos probabilísticos ajudará a reforçar minha base de probabilidade (que é bem fraca).

O curso de processamento de linguagem natural eu peguei mais por curiosidade e ainda não decidi se vou realmente fazer.

Comentários Desativados em Retrospectiva 2011 | pessoal | Permalink
Publicado por kunigami

SRM 527

Dezembro 25, 2011

Depois de quase 5 anos competindo no Topcoder, finalmente meu rating ficou amarelo (+1500) \o/. Entretanto, não acredito que eu vá sustentar essa cor por muito tempo.

Como de costume comecei pelo problema fácil (275). Como não consegui pensar em nenhuma solução além de uma força-bruta complicada e como a pontuação do problema médio estava menor do que o de costume (450 contra 500), resolvi lê-lo. Então vamos começar por ele.

P8XMatrixRecovery

(Enunciado do problema)

Minha primeira ideia foi modelar como emparelhamento bipartido máximo de custo mínimo, mas não estava conseguindo modelar a função objetivo.

Depois de pensar mais, acabei lembrando de uma técnica que consiste em fixar um parâmetro do problema visando simplificá-lo. Um caso especial dessa técnica é o uso de busca binária num problema de otimização para transformá-lo em um problema de decisão.

Um problema que me lembro que pode ser resolvido com a técnica mais geral é o seguinte: encontrar o emparelhamento máximo de um grafo bipartido de forma que se minimize o custo da aresta de maior custo (a versão clássica do emparelhamento máximo de custo mínimo seria minimizar a soma dos custos das arestas).

A solução é, para cada possível custo de aresta C, criar um subgrafo G' contendo apenas as arestas de custo menores ou iguais a C. A resposta será o menor C para o qual existe um emparelhamento máximo em G'.

No problema em questão, podemos ter várias permutações de colunas que mapeiam uma matriz na outra, por causa dos caracteres coringas (‘?’). Entretanto, o problema pede a lexicograficamente menor. A ideia é fixar o primeiro caractere ‘?’ em ‘0’ e verificar se ainda existe um mapeamento.

Se sim, então podemos manter o caractere em ‘0’ e proceder para o próximo caractere ‘?’. Caso contrário, não existe nenhum mapeamento com ‘0’ e como o enunciado diz que sempre existe uma solução, então tem que existir alguma com ‘1’ e portanto podemos trocar para esse valor. Fazendo isso para todo caractere ‘?’ encontraremos a matriz lexicograficamente menor.

Para decidir se existe um mapeamento podemos resolver o problema do emparelhamento máximo bipartido. Criamos duas partições com vértices correspondendo a cada coluna de cada matriz. Adicionamos uma aresta entre dois vértices se as colunas correspondentes são iguais. Note que o “igual” nesse caso deve levar em conta que ‘?’ é igual a ‘?’, ‘0’ ou ‘1’. Se houver um emparelhamento perfeito, significa que existe uma bijeção entre as colunas das duas matrizes.

O emparelhamento máximo bipartido pode ser resolvido através do algoritmo de caminhos de aumento (augmenting paths) com complexidade O(NM) onde N é o número de vértices e M é o número de arestas.

Note que devemos resolver o problema do emparelhamento para cada ‘?’. No pior caso podemos ter matrizes só com ‘?’ (N^2) e nesse caso o grafo bipartido teria O(N^2) arestas, levando a uma complexidade total O(N^5). No problema o valor de N era igual a 30. Eu achei que ia estourar, mas minha solução acabou passando (código no github).

P8XGraphBuilder

(Enunciado do problema)

Depois que resolvi o problema médio, voltei a pensar na solução para esse problema. Cheguei a pensar na seguinte proposição:

Proposição: Dado um vetor de N elementos com valores maiores ou iguais a 1 e de tal forma que a soma desses elementos seja 2(N-1), é possível construir uma árvore de N vértices, de forma que exista uma correspondência entre os graus dos vértices e os elementos desse vetor.

Por exemplo, se N = 4, temos os vetores [3, 1, 1, 1] e [2, 2, 1, 1] e suas permutações. Dado um vetor, seu custo é dado pela soma dos pesos de seus elementos. O problema original então se reduz a encontrar o maior custo de um vetor satisfazendo as restrições da proposição.

É possível resolver esse novo problema através de programação dinâmica. Podemos definir C(n, s) como a melhor solução de um vetor de n elementos e somando exatamente s. A recorrência fica:

C(n, s) = \max_{d=1}^{N-1} C(n - 1, s - d) + b(d)

Onde b(d) é o valor do elemento d (dado pelo vetor scores). A base é quando n = 0. Nesse caso, se s = 0, temos 0, caso contrário não existe solução e retornamos -\infty.

Durante a prova, não tinha cheguei a provar a proposição, mas ela me pareceu correta. Mas infelizmente não tive tempo de implementar essa solução, que agora adicionei ao github.

Pra fins de completude, vou apresentar agora a prova da proposição.

Prova: Primeiro, sem perda de generalidade, vamos supor que os elementos do vetor estão ordenados em ordem não-crescente. Vamos usar um argumento construtivo. Dado um vetor v = \{d_1, d_2, \cdots, d_N\}, seja k o número de elementos com valor maior ou igual a 2. Crie um nó raíz com d_1 filhos. Faça um desses filhos ter d_2 - 1 filhos, um dos “netos” ter d_3 - 1 filhos e assim sucessivamente, até um nó ter d_k - 1 filhos.

Por exemplo, dado o vetor v = {4,4,3,1,1,1,1,1,1,1} construímos a árvore da figura abaixo.

Árvore com graus {4,4,3,1,1,1,1,1,1,1}

Temos uma árvore onde k nós têm grau igual aos primeiros k elementos de v e o resto dos nós têm grau 1. Resta provar que o número desses nós de grau 1 é exatamente N - k, ou equivalentemente, que essa árvore tem N nós. É fácil ver que o número de filhos “gerados” é a soma d_1 + (d_2 - 1) + (d_3 - 1) + \cdots + (d_k - 1) = (\sum_{i = 1}^k d_i) - k + 1.

O único vértice que não foi contado acima foi a raíz, então se N' é o número de nós da árvore gerada, temos N' = (\sum_{i = 1}^k d_i) - k + 2.

Usando a restrição de que o vetor deve somar 2(N-1), com um pouco de álgebra:

\sum_{i = 1}^k d_i + \sum_{i = k+1}^N d_i = 2N - 2

\sum_{i = 1}^k d_i + (N-k) = 2N - 2

Concluímos que N = (\sum_{i = 1}^k d_i) - k + 2 e que N' = N

Comentários Desativados em SRM 527 | grafos, programação dinâmica, topcoder | Permalink
Publicado por kunigami

Linearização de desigualdades não-lineares

Dezembro 18, 2011

Há algum tempo atrás, assisti uma apresentação em que o palestrante chegou a uma equação não linear e disse que era possível linearizá-la, entretanto sem dizer como, apenas passando uma referência.

Não consegui encontrar a referência na época, mas recentemente alguém postou no OR Exchange (sistema semelhante ao StackOverflow, mas voltado à Pesquisa Operacional) uma dúvida relacionada. Uma das respostas passou uma referência para um documento do AIMMS chamado Integer Programming Tricks [1].

Nesse documento há algumas técnicas de modelagem de programação linear inteira. Algumas delas eu já conhecia como por exemplo modelar restrições disjuntas (quando exatamente uma de duas restrições deve ser satisfeita).

A novidade é a técnica usada para transformar um produto de duas variáveis, por exemplo x_1 \cdot x_2, em uma equação linear. Há três casos que devemos considerar: quando ambas variáveis são binárias; quando uma das variáveis é binária e a outra é contínua; e quando as duas variáveis são contínuas.

Caso 1: Ambas variáveis binárias

No caso em que ambas x_1 e x_2 são binárias, a modelagem é fácil:

(1) \, y \le x_1

(2) \, y \le x_2

(3) \, y \ge x_1 + x_2 - 1

(4) \, y \in \{0, 1\}

Fazendo as 4 possíveis combinações de valores, é fácil ver que y = x_1 \cdot x_2.

Caso 2: Uma das variáveis é contínua

A formulação nesse caso não é muito diferente. Vamos supor que é x_2 a variável contínua e é limitada por 0 \le x_2 \le u. Temos:

(5) \, y \le u \cdot x_1

(6) \, y \le x_2

(7) \, y \ge x_2 - u(1 - x_1)

(8) \, y \ge 0

Se x_1 = 0, temos que y = 0. Se x_1 = 1, então (7) vira y \ge x_2, que combinado com (6), implica y = x_2.

Caso 3: Ambas as variáveis contínuas

Esse caso é bem mais complicado e requer a introdução de um novo conceito: formulações lineares por partes (numa tradução livre de piecewise linear formulation).

Formulação linear por partes

Essa técnica consiste em aproximar uma dada função/restrição não-linear por uma função linear por partes, e é bastante comum em métodos numéricos.

Uma função é linear por partes (piecewise linear function) se pudermos subdividir o domínio em intervalos nos quais a função é linear.

x

Função não linear aproximada por uma função linear por partes

As funções que podem ser aproximadas por essa técnica devem ser separáveis. Uma função é separável se ela pode ser escrita como a soma de funções que só dependem de uma variável. Por exemplo, x_1^3 + x_2^2 é separável, mas x_1 \cdot x_2 não é.

Assim, dada uma função separável, considere uma função g do somatório. Suponha que aproximamos g usando uma função linear por partes f, com intervalos definidos pelos pontos x_1, x_2, \cdots, x_n, sendo que a função f entre x_i e x_{i+1} é linear.

Podemos modelar a função f(x) através de programação linear. Para isso, considere as variáveis contínuas \lambda_i, tal que 0 \le \lambda_i \le 1. Temos então

(9) \, \sum_{i=1}^n \lambda_i = 1

(10) \, f(x) = \sum_{i=1}^{n} f(x_i) \lambda_i

(11) \, x = \sum_{i=1}^{n} x_i \lambda_i

Com a restrição adicional de que no máximo dois \lambda‘s sejam não nulos e no caso de serem dois, esses \lambda‘s devem ser consecutivos. A ideia é que se só um \lambda_i for não nulo, ele representa x_i e f(x_i). No caso de \lambda_i e \lambda_{i+1} serem não nulos, eles representam x' = x_i \lambda_i + x_{i+1} \lambda_{i+1} e f(x') = f(x_i) \lambda_i + f(x_{i+1}) \lambda_{i+1}.

Note que como \lambda_i + \lambda_{i+1} = 1, [x', f(x')] é uma combinação convexa de [x_i, f(x_i)] e [x_{i+1}, f(x_{i+1})] e portanto pertence à reta que une esses dois pontos.

Essa restrição pode ser embutida no algoritmo do simplex. Para isso, os resolvedores de programação linear inteira usam o SOS2 (Special Order Sets 2), no qual devemos especificar o conjunto de variáveis x_i e f(x_i) (os SOS2 não tem nada a ver com SOS1, sobre o qual falei num post anterior).

Entretanto, alguns resolvedores como o GLPK não possuem essa funcionalidade embutida. Em [2], eles apresentam uma formulação de PLI para modelar essa restrição.

São introduzidas novas variáveis binárias, z_i para i = 1, \cdots, n-1. Temos que z_i = 1 se e somente se, o valor de x está entre x_i e x_{i+1}. Também introduzimos uma variável contínua s_i para i = 1, \cdots, n-1, onde 0 \le s_i \le 1. Nesse caso s_i representa a combinação convexa entre x_{i} e x_{i+1}.

Definindo y_i = f(x_i) para i = 1, \cdots, n e y = f(x), temos o seguinte conjunto de restrições:

(12) \, \sum_{i = 1}^{n-1} z_i = 1

(13) \, s_i \le z_i

(14) \, x = \sum_{i = 1}^{n-1} x_i z_i + (x_{i+1} - x_{i}) s_i

(15) \, y = \sum_{i = 1}^{n-1} y_i z_i + (y_{i+1} - y_{i}) s_i

Como z_i‘s são binárias, exatamente um z_j será igual a 1 (e o resto zero). Nesse caso, (14) reduzirá para:

x = x_j + (x_{j + 1} - x_{j}) s_j,

que podemos reescrever como

x = x_j (1 - s_j) + x_{j+1} s_j

Para a equação (15) teremos, de maneira análoga:

y = y_j (1 - s_j) + y_{j+1} s_j

Ficando mais evidente ver que [x, y] é combinação convexa de [x_j, y_j] e [x_{j+1}, y_{j+1}].

Eliminação do produto de variáveis diferentes

Agora que vimos como fazer a formulação linear por partes, vamos ver como linearizar x_1 \cdot x_2 supondo que ambas são contínuas.

Para esse fim, definimos duas variáveis y_1 = \frac{1}{2} (x_1 + x_2) e y_2 = \frac{1}{2} (x_1 - x_2). Agora é fácil ver que y_1^2 - y_2^2 = x_1 \cdot x_2, e é uma função separável.

Agora podemos usar a formulação apresentada anteriormente da seguinte forma: aproximar y_1^2 usando k pontos (note o tradeoff entre precisão e tempo de execução), gerando pares [{y_1}_i, {y_1}_i^2] para i = 1, \cdots, k. Agora basta substituir ocorrência de y_1 pelo ‘x’ de (14) e y_1^2 pelo ‘y’ da equação (15). Repetimos o mesmo procedimento para a função -y_2^2.

Pronto! Agora todas as restrições do modelo são lineares!

Conclusão

Aprendi uma técnica muito útil para atacar alguns problemas com funções/restrições não-lineares. Ainda pretendo aprender programação não-linear, quer cursando uma disciplina, quer estudando um livro por conta.

Fiquei na dúvida sobre como aproximar uma função com domínio muito grande. Podem ser necessários muitos intervalos para uma boa aproximação e o número de variáveis cresce proporcionalmente.

Outra pergunta que não sei responder é o que dá para fazer quando ambas as variáveis são inteiras. É possível transformar uma variável inteira em binária, mas novamente, dependendo do tamanho do domínio das variáveis inteiras, a formulação pode ficar com um tamanho demasiadamente grande. Será que existe um jeito mais eficiente de linearizar x_1 \cdot x_2 nesse caso?

Só descobri esse material graças ao tópico no OR Exchange. Por sua vez, só fiquei sabendo do tópico graças ao twitter do OR Exchange. Aliás, tenho conseguido usar o twitter como ferramenta para obtenção de informações (úteis!). A maior parte das contas que passei a seguir ultimamente são agregadores de notícias/links relacionados à pesquisa operacional.

Referências

[1] AIMMS Modelling Guide – Integer Programming Tricks
[2] SOS2 constraints in GLPK

Comentários Desativados em Linearização de desigualdades não-lineares | programação linear inteira | Permalink
Publicado por kunigami

Java Servlets no Tomcat

Dezembro 11, 2011

Nesse post vou comentar um pouco sobre Servlets e um exemplo básico de utilização usando o Tomcat.

O que são Servlets?

Segundo a Wikipedia, um Servlet é uma classe Java usada para estender a funcionalidade de um servidor, sendo capaz de receber e enviar mensagens via um protocolo cliente-servidor (em geral HTTP).

Aplicações que utilizam a API de Servlets podem ser disponibilizadas na web através de um Web Container. Há diversos Web Container’s grátis, como por exemplo, o GlassFish (da própria Oracle), o JBoss AS (da Red Hat) e o Tomcat (da Apache). Podemos pensar em Web Conteiner’s como bibliotecas que implementam a API de Servlets.

A versão da API de Servlets que vamos utilizar é a 3.0 (Java EE6). Essa versão é suportada pelas seguintes versões dos Web Container’s citados acima: GlasshFish +3, JBoss AS +7 e Tomcat +7. Em nosso exemplo usaremos o Tomcat 7.

O build e o deploy do código serão feitos através do Maven.

Tomcat 7

Antes de mais nada, vamos instalar e configurar o Tomcat 7. Para instalar, basta baixar os .jar diretamente do site do Tomcat em um diretório qualquer. A partir de agora vamos nos referir ao local de instalação como $TOMCAT_DIR. Na pasta $TOMCAT_DIR/bin, podemos iniciar o Tomcat através do script startup.sh.

Para verificar se o Tomcat foi corretamente iniciado, podemos entrar no endereço localhost:8080.

Podemos gerenciar o Tomcat via web, mas para isso, precisamos adicionar um usuário no arquivo $TOMCAT_DIR/conf/tomcat-users.xml. Nesse arquivo xml, adicione a seguinte entrada dentro da tag <tomcat-users>:

<role rolename="manager-gui"/>
<role rolename="manager-script"/>
<user username="nome-usuario" password="senha" roles="manager-gui, manager-script"/>

trocando "nome-usuario"/"senha" por valores adequados. É preciso reiniciar o Tomcat (shutdown.sh + startup.sh). Agora você deverá poder acessar a página localhost:8080/manager com o usuário e senhas cadastrados.

Servlet Java

A estrutura de diretórios do nosso exemplo é a seguinte:

|-- pom.xml
 `-- src
     `-- main
         |-- java
         |   `-- me
         |       `-- kuniga
         |           `-- main
         |               `-- MyApp.java
         |-- resources
         |
         `-- webapp
             `-- WEB-INF

A implementação da nossa única classe é baseada em [4]. Uma das novidades da API de Servlets 3.0 é o uso de anotações para configuração, como podemos ver no código a seguir:

@WebServlet("/MyApp")
public class MyApp extends HttpServlet {

  @Override
  protected void doGet(HttpServletRequest request,
                       HttpServletResponse response)
      throws ServletException, IOException {

    String nome = request.getParameter("nome");

    PrintWriter out = response.getWriter();
    out.println("Ola: " + nome);
  }
}

O argumento passado para a anotação WebServlet definirá a url de acesso à nossa aplicação. Já o método doGet será invocado quando uma requisição do tipo GET for feita. O conteúdo passado para o PrintWriter será retornado para o cliente.

Para compilar o código acima, devemos incluir a API 3.0 de Servlets. Podemos fazer isso incluindo uma dependência das APIs do Java EE6:

<dependency>
  <groupId>javax</groupId>
  <artifactId>javaee-api</artifactId>
  <version>6.0</version>
  <scope>provided</scope>
</dependency>

É importante setar o escopo como provided para que o maven não coloque o .jar contendo as APIs do Java EE6 no arquivo .war. Isso porque no Tomcat esse .jar já está presente e a duplicata ocasiona erro. (Aliás, uma dica para debugar erros é iniciar o Tomcat através do comando ./catalina.sh run ao invés do ./startup.sh, pois desta forma as mensagens de log são exibidas no terminal).

Configurando plugins do Maven

Basicamente o que o maven fará é compilar o programa e compactá-lo em um arquivo .war e então fará o deploy desse arquivo no Tomcat.

Vamos primeiramente configurar o plugin maven-war-plugin, que é responsável por gerar o arquivo .war. Em versões anteriores da API de Servlets, era necessário um arquivo de configuração chamado web.xml que ia em webapp/WEB-INF. Agora, a configuração básica pode ser feita através de anotações na classe do servlet e o arquivo web.xml não é obrigatório.

Por padrão, o plugin maven-war-plugin gera um erro na ausência do web.xml, mas podemos modificar esse comportamento através da seguinte configuração no pom.xml:

<plugin>
  <artifactId>maven-war-plugin</artifactId>
  <configuration>
    <failOnMissingWebXml>false</failOnMissingWebXml>
  </configuration>
</plugin>

O outro plugin que iremos configurar é o tomcat-maven-plugin, responsável pelo deploy no tomcat. Para isso, ele precisa da url de acesso ao manager, bem como um login válido para acessá-la. Podemos passar os dados de login através do pom.xml.

Mais especificamente, adicionamos uma entrada no settings.xml do maven, que se encontra em ~/.m2/settings.xml (mais informações sobre esse arquivo aqui). 

<server>
  <id>mytomcat</id>
  <username>nome-usuario</username>
  <password>senha</password>
</server>

Onde id é um identificador qualquer, e username e password são aqueles que usamos no cadastro de usuário no Tomcat. No pom.xml do projeto passamos essa informação de login e a url da página:

<plugin>
  <groupId>org.codehaus.mojo</groupId>
  <artifactId>tomcat-maven-plugin</artifactId>
  <configuration>
    <url>http://localhost:8080/manager/html</url>
    <server>mytomcat</server>
  </configuration>
</plugin>

A versão completa do pom.xml está aqui e também disponibilizei o projeto todo no github.

Agora podemos executar os seguintes goals do maven:

> mvn clean package tomcat:deploy

Rodando a aplicação

Para testar a aplicação em funcionamento, podemos acessar a seguinte url: http://localhost:8080/kservlet/MyApp?nome=mundo

Referências

[1] Java Servlet – Página oficial da Oracle
[2] Java Servlet – Wikipedia
[3] How do I deploy a maven web application to Tomcat?
[4] Blog Caelum – Java EE6: Começando com as Servlets 3.0
[5] Tomcat 6.0.32 + Maven undeploy via script not working

1 Comentário | java | Tagged: , | Permalink
Publicado por kunigami

Haskell – Typeclass

Dezembro 4, 2011

Neste post vou comentar sobre a estrutura typeclass do Haskell. A minha principal referência é o capítulo 6 do Real World Haskell.

Typeclasses

Como em Haskell existem tipos parametrizados, podemos querer definir funções que aceitam parâmetros com esse tipo. Entretanto, provavelmente a implementação da função será diferente para cada tipo.

Assim, typeclass é uma estrutura para prover essa funcionalidade. A sintaxe básica é a seguinte:

class <Nome> <Tipos parametrizados> where
    <função 1> :: <Assinatura de tipos>
    <função 2> :: <Assinatura de tipos>

Apesar do nome, um typeclass é bem diferente de uma classe que estamos acostumados em linguagens orientadas à objetos.

Um caso onde typeclass é útil é na implementação do operador de igualdade. Suponha que temos dois tipos Booleano e CorRGB:

data CorRGB = Vermelho | Verde | Azul
     deriving (Show)

data Booleano = Falso | Verdadeiro
     deriving (Show)

Podemos definir uma typeclass contendo uma função de igualdade, que recebe dois parâmetros de um mesmo tipo parametrizado a, e retorna True se forem iguais ou False caso contrário.

class Compara a where
      igual :: a -> a -> Bool

Aí podemos definir uma implementação para cada tipo, usando uma estrutura chamada instance. A sintaxe é semelhante ao typeclass, mas agora especificamos os tipos parametrizados e definimos a implementação da função. Para o caso do Booleano e da CorRGB, temos:

instance Compara Boolean where
         igual Verdadeiro Verdadeiro = True
         igual Falso Falso = True
         igual _ _  = False

instance Compara RGBColor where
         igual Vermelho Vermelho = True
         igual Verde Verde = True
         igual Azul Azul = True
         igual _ _ = False

Também podemos prover implementações padrões para um typeclass, definindo a implementação na estrutura class. Na execução, a implementação utilizada é sempre a mais específica.

Complementando o exemplo da typeclass Compara, podemos definir a função diferente e definir implementações padrões para ela e também para a função igual:

class Compara a where
      igual :: a -> a -> Bool
      igual x y =  not (diferente x y)

      diferente :: a -> a -> Bool
      diferente x y = not (igual x y)

Derivação automática

Na definição de Booleano e CorRGB, usamos a diretiva deriving(Show). Essencialmente Show é um typeclass da biblioteca padrão. A função show desse typeclass transforma um tipo genérico em String.

Fazendo alguns testes no terminal (ghci):

> show(Vermelho)
"Vermelho"
> :type show
show :: Show a => a -> String

Note que o comando :type usa uma sintaxe diferente para dizer que a função show pertence ao typeclass Show.

Podemos escrever nossa própria implementação para CorRGB ao invés de usar o padrão. Para isso, removemos a declaração deriving(Show) e adicionamos:

instance Show CorRGB where
         show Vermelho = "Red"
         show _ = "Not implemented"

Segundo [2], a funcionalidade do derive só pode ser usada com um conjunto específico de built-in typeclasses.

Typeclass com lista de tipos paramétricos

Imagine que queiramos implementar a função igual para uma lista de Booleanos. A primeira tentativa seria:

instance Compara [Boolean] where
         igual = undefined

No código acima, undefined é um tipo coringa que não causa erros de compilação devido a incompatibilidade de tipos, mas que causa um erro em tempo de execução. Essa técnica de usar undefined‘s é interessante para ir compilando versões intermediárias do seu código mesmo sem ter a implementação de todas as funções.

Enfim, veremos que tal trecho de código leva ao seguinte erro de compilação:

   Illegal instance declaration for `Compara [Boolean]'
      (All instance types must be of the form (T a1 ... an)
       where a1 ... an are *distinct type variables*,
       and each type variable appears at most once in the instance head.
       Use -XFlexibleInstances if you want to disable this.)
    In the instance declaration for `Compara [Boolean]'
Failed, modules loaded: none.

Há diversas maneiras de se contornar esse erro. Um deles é definir uma função exclusiva para listas, no caso da função igual, podemos criar uma igualLista,

class Compara a where
  ...
  igualLista :: [a] -> [a] -> Bool
  igualLista (xa:a) (xb:b) | diferente xa xb = False
                           | otherwise = igualLista a b
  igualLista [ ] [ ] = True
  igualLista _ _ = False
  ...

A vantagem nesse caso é que a implementação padrão deverá servir para a maior parte dos casos, pois em geral o teste de igualdade entre duas listas consiste em verificar se todos os elementos em ambas são iguais.

No caso de você querer definir a implementação apenas para uma lista de um tipo particular (p. e. [Booleano]), pode-se encapsular essa lista em uma estrutura chamada newtype.

O newtype é parecido com um tipo de dado algébrico (keyword data), com algumas diferenças como por exemplo o newtype exigir exatamente um data constructor e o tipo de um newtype é resolvido em tempo de compilação, ao contrário do data, e por isso seu uso não ocasiona overhead na execução do programa [1].

Assim, poderíamos fazer:

newtype Wrapper = Wrapper [Booleano]

Agora podemos implementar a função, com o inconveniente de encapsular os dados do novo tipo com Wrapper:

instance Compara Wrapper where
  igual (Wrapper x) (Wrapper y) = igualAux x y
    where igualAux (xa:a) (xb:b) | diferente xa xb = False
                                 | otherwise = igualAux a b
          igualAux [ ] [ ] = True
          igualAux _ _ = False

Uma boa referência para essas e outras alternativas é o haskell wiki [3].

Conclusão

Achei esse assunto bem complicado! Pra piorar, parece que o livro Real World Haskell no qual estou me baseando, escreveu muito mal os capítulos 5 e 6, dando exemplos muito complexos (talvez seja a diretriz do “real world”, mas definitivamente isso não é didático), confusos e chatos. Há diversos comentários que compartilham dessa opinião.

Apesar de tudo, continuarei meus estudos com esse livro, mesmo que eu só use os tópicos para me guiar e procurar explicações em referências como [2] e [3].

Referências

[1] http://book.realworldhaskell.org/read/using-typeclasses.html
[2] http://en.wikibooks.org/wiki/Haskell/Class_declarations
[3] http://www.haskell.org/haskellwiki/List_instance

1 Comentário | haskell, livro | Permalink
Publicado por kunigami