Haskell – Tipos de Dados Algébricos

Setembro 25, 2011

Haskell usa uma sintaxe elegante para representar um tipo de estrutura de dados, análoga a diversas outras estruturas presentes em linguagens como C e C++. Essas estruturas são chamadas tipos de dados algébricos. Minha principal referência para esse post foi o capítulo 3, do livro Real World Haskell.

Este é o segundo post sobre meus estudos em Haskell. O primeiro se encontra aqui.

Struct

Considere a seguinte struct em C++ representando um livro através de seu código, título e autores:

#include <string>
#include <vector>
struct {
    int isbn;
    std::string title;
    std::vector < std::string > authors;
};

Em haskell podemos escrever:

data BookInfo = Book Int String [String]
                deriving (Show)

Para definir essa estrutura, deve-se iniciar com a keyword data e dar um nome para esse novo tipo, no caso BookInfo (chamado de type constructor). Além disso, definimos um construtor desse tipo, que no exemplo tem o nome Book (chamado de value constructor ou data constructor), mas poderia ter o mesmo nome do tipo. Tanto o nome do construtor quanto o nome do tipo devem ser iniciados por letra maiúscula.

A linha deriving (Show) está sendo usada nesse e nos outros exemplos deste post para que uma instância desse estrutura possa ser impressa no terminal. Podemos instanciar a estrutura BookInfo da seguinte forma:

myBook = Book 9780135072455 "Algebra of Programming"
         ["Richard Bird", "Oege de Moor"]

Note que os parâmetros de entrada devem estar na mesma ordem em que eles são definidos na estrutura.

Note também que os “membros” dessa estrutura são anônimos, sendo representados apenas por seu tipo. Para contornar a possível perda de legibilidade, é possível usar sinônimos de tipos, através da keyword type (parecido com o typedef de C++).

type ISBN = Int
type Title = String
type Author = String

data BookInfo = Book ISBN Title [Author]
                deriving (Show)

Enum

Outra estrutura em C++ que pode ser representada sucintamente em Haskell é o enum. Considere um enum representando as cores RGB:

enum Color { Red, Green, Blue };

Um tipo de dado algébrico admite mais de um construtor, desde que tenham nomes diferentes. Além disso, os construtores não precisam ter parâmetros, o que permite escrever o enum acima da seguinte forma:

data Color = Red | Green | Blue
             deriving (Show)

Union

Ainda aproveitando que podemos ter vários construtores com diferentes parâmetros, podemos também representar uma union. Considere o seguinte exemplo em C++ de uma union podendo representar duas formas geométricas – um círculo ou um polígono:

struct Point {
    double x, y;
};
struct Circle {
    Point center;
    double radius;
};
struct Polygon {
    int nvertices;
    Point *vertices;
};
union Shape {
    Circle circle;
    Polygon polygon;
};

Em Haskell, é possível fazer o seguinte:

type Point = (Double, Double)
type Center = Point
type Radius = Double

data Shape = Circle Center Radius
           | Polygon [ Point ]
             deriving (Show)

Curiosidade: Na especificação atual do C++ (2003), membros de uma union não podem ter construtores não-triviais. Parece porém, que na nova especificação (C++11) será possível. Portanto, o exemplo abaixo não compila com gcc-4.2.1:

#include <utility>
#include <vector>

typedef std::pair <double, double> Point;
typedef std::vector<Point> Polygon;

struct Circle {
    Point center;
    double radius;
};

union Shape {
    Circle circle;
    Polygon polygon;
};

Getters e Setters

Quando trabalhamos com classes, eventualmente queremos proteger o acesso de leitura/escrita a seus membros usando getters e setters, como por exemplo:

#include <string>
class Person {
    int id;
    std::string name;

public:

    int get_id(){ return id; }
    void set_id(int _id){ id = _id; };
    std::string get_name(){ return name; }
    void set_name(std::string &_name) { name = _name; }
};

Há um mecanismo parecido em Haskell, implementado pelo chamado record syntax. Num exemplo análogo ao anterior:

type ID = Int
type Name = String

data Person = Person {
      personID      :: ID,
      personName    :: Name
      } deriving (Show)

Essa sintaxe mais verbosa permite instanciar a estrutura atribuindo os parâmetros aos membros explicitamente como:

you = Person {personName = "YourName", personID = 2}

O getter de um membro é dado por:

personName you

Enquanto o setter seria:

you {personID 3}

Tipos Parametrizados

Tipos de dados algébricos representam ainda outra funcionalidade presente em C++: templates. Tomemos como exemplo uma classe representando um ponteiro genérico para qualquer tipo:

template <typename T>
struct GenericPointer {
    T* ptr;
};

Ao instanciar essa classe podemos definir os tipos que queremos representar:

int i = 2;
GenericPointer<int> p1;
p1.ptr = &i;
GenericPointer<double> p2;
p2.ptr = NULL;

Aqui temos ponteiros para os tipos int e double, sendo que o NULL é um valor genérico para dizer que o ponteiro não aponta pra lugar algum.

Uma analogia (forçada) em Haskell seria a seguinte:

data GenericPointer a = Ptr a |
                        Null
                        deriving(Show)

Embora em Haskell não tenhamos o valor NULL, podemos simulá-lo através de um construtor como no exemplo acima. Esse encapsulamento é particularmente interessante para prover uma condição de exceção. Por exemplo, considere uma função que retorna o primeiro elemento de uma lista:

first_elem (x:xs) = x

O que retornar caso a lista seja vazia? Uma solução seria usar o encapsulamento:

first_elem (x:xs) = Ptr x
first_elem _      = Null

No exemplo, o caractere '_' funciona como um coringa, ou seja, qualquer parâmetro casa com ele. Como foi posto depois do outro padrão, ele se comporta como um “else” e só será chamado quando a lista não tiver elementos.

Tipos Recursivos

Outra possibilidade de um tipo de dado algébrico é usar tipos recursivos, isto é, membros da estrutura são do tipo dessa estrutura. Em C e C++ é possível fazer isso utilizando ponteiros. Por exemplo, podemos implementar uma lista ligada de elementos genéricos da seguinte maneira:

template <typename T>
struct LinkedList {
    LinkedList<T>* next;
};

Em Haskell temos algo como:

data LinkedList a = Node a (LinkedList a)
            | Null 
            deriving(Show)

Para representar uma lista ligada contendo 3, 1 e 2, nessa ordem, usamos a seguinte sintaxe:

Node 3 (Node 1 (Node 2 Nil))

Um árvore binária também é bem simples de se representar:

data Tree a = Node a (Tree a) (Tree a)
            | Null
              deriving (Show)

Conclusão

Haskell tem uma sintaxe sucinta para descrever tipos de dados algébricos, que por sua vez são bastante versáteis, podendo representar tanto estruturas quanto uniões, enumerações, classes, etc.

Ainda sei muito pouco sobre a linguagem, mas por enquanto estou achando-a bastante interessante.

Anúncios

Google Code Jam 2011

Setembro 18, 2011

O Google Code Jam é uma competição de algoritmos anual promovida pelo Google, que acontece desde 2007 se não me engano. Esse ano eu fui até o round 2, mas acabei não me classificando entre os 500 primeiros para avançar ao round 3:( Entretanto, acabei ganhando um prêmio de consolação por ter ficado entre os 1000 primeiros, que é a camiseta do evento.

Camiseta (frente)

Embora a competição tenha acabado em Julho, a camiseta só chegou a algumas semanas. O desenho na parte de trás são linhas de código em diversas linguagens de programação e tem o formato do Japão que é onde foi a final mundial, na qual o japonês Makoto Soejima (rng_58 no topcoder) sagrou-se vencedor.

Detalhe da parte de trás

Com a chegada da camiseta, lembrei que eu tinha ficado de estudar a solução dos problemas do round 2 que eu não havia conseguido resolver. Felizmente os problem setters apresentam a solução, mas também vou descrevê-las aqui do meu jeito.

C. Expensive Dinner

O enunciado desse problema está aqui. A solução está baseada em três proposições principais.

Proposição 1: Dado um grupo de amigos x_1, x_2, \dots, x_i, o valor da conta é sempre LCM(x_1, x_2, \dots, x_i) não importa a ordem em que eles cheguem. LCM representa o mínimo múltiplo comum.

Prova: Seja y o valor da conta.

Parte 1 – mostrar que y \ge LCM(x_1, x_2, \dots, x_i)
Essa parte é direta, dada a definição de mínimo múltiplo comum e que a conta tem que ser divisível por todo x_i.

Parte 2 – mostrar que y \le LCM(x_1, x_2, \dots, x_i)
Quando um amigo x_i pede alguma coisa, o valor da conta vai para o próximo múltiplo de x_i. Como LCM(x_1, x_2, \dots, x_i) é múltiplo de todos, o valor da conta não poderá “pular” esse valor e uma vez que esteja nesse valor, todos estarão satisfeitos e a conta não irá mais aumentar.

Juntando as partes 1 e 2, provamos a proposição.

Seja M o número de vezes que o garçon é chamado e M_{\max} e M_{\min} o maior e o menor valor possível de M, respectivamente. O problema pede M_{\max} - M_{\min}. Sejam p_1, p_2, \dots, p_P os P primos menores ou iguais a n (o número de amigos). Além do mais, seja e_i o maior inteiro tal que p_i^{e_i} \le n.

Proposição 2: M_{\max} = 1 + \sum_{i=1}^P{e_i}

Prova: vamos quebrar em duas partes novamente.

Parte 1 – mostrar que M_{\max} \ge 1 + \sum_{i=1}^P{e_i}
Para isso basta exibir um caso onde M = 1 + \sum_{i=1}^P{e_i}. Esse é o caso em que os amigos chegam na ordem 1, 2, \dots, n. Considere a chegada de x_i tal que x_i = p_i^k. É fácil ver que LCM(x_1, x_2, \dots, x_{i-1}) não é divisível por p_i^k e portanto o garçon terá de ser chamado. Quantos x_i existem satisfazendo x_i = p_i^k? Justamente \sum_{i=1}^P{e_i}. Além disso, quando x_1 = 1 chegar a primeira vez, o garçon também deverá ser chamado. Portanto, o número de vezes que o garçon foi chamado é pelo menos 1 + \sum_{i=1}^P{e_i}

Parte 2 – mostrar que M_{\max} \le 1 + \sum_{i=1}^{e_i}
Pela Proposição 1, o valor final da conta deverá ser LCM(x_1, x_2, \dots, x_n), que é igual a \prod_{i=1}^P p^{e_i}. Para qualquer ordem de amigos, temos LCM(x_1, x_2, \dots, x_i) = k \cdot LCM(x_1, x_2, \dots, x_{i-1}) para um inteiro k. É fácil ver que se um garçon for chamado, então k > 1, ou seja, estamos aumentando a potência que algum fator primo até chegarmos em \prod_{i=1}^P p^{e_i}, logo o garçon não pode ser chamado mais do que o número total de fatores na conta final, ou seja, \sum_{i=1}^{e_i} (+1 por causa da primeira chamada).

Juntando as partes 1 e 2, provamos a proposição.

Proposição 3: M_{\min} = P

Prova: vamos quebrar em duas partes novamente.

Parte 1 – M_{\min} \le P
Para isso basta exibir um caso onde M = P. Considere uma ordem onde os P primeiros amigos a entrarem são exatamente aqueles iguais a p_i^{e_i} para todo i = 1, \dots, P. É fácil ver que depois que eles entratem, o valor da conta será já LCM(x_1, x_2, \dots, x_n) e todo mundo que entrar depois já estará satisfeito, tendo o garçon sido chamado apenas P vezes.

Parte 2 – M_{\min} \ge P
Vamos por contradição: suponha que existe uma ordem de P-1 ou menos amigos tal que LCM(x_1, x_2, \dots, x_{P-1}) = LCM(x_1, x_2, \dots, x_n) = \prod_{i=1}^P p^{e_i}. Note que, para cada p_i, deve existir um amigo com fator p_i^{e_i} (caso contrário o LCM seria menor). Pelo princípio das casas dos pombos, como existem apenas P-1 amigos e P primos, há de haver algum amigo múltiplo de p_i^{e_i} e p_j^{e_j}. Entretanto, ambos p_i^{e_i} e p_j^{e_j} são maiores que \sqrt{n}. Isso implica que esse amigo tem valor maior que n, uma contradição.

Juntando as partes 1 e 2, provamos a proposição.

Dadas essas proposições, o problema se reduz a calcular (1 + \sum_{i=1}^P {e_i}) - P para todo primo P \le n. Considerando que podemos calcular e_i em O(\log(n)), levando a um algoritmo O(n \log(n)). Porém, como n pode ser até 10^{12}, temos que fazer melhor.

A sacada é reescrever a equação como 1 + \sum_{i=1}^P ({e_i} - 1). Isso quer dizer que só estamos interessados em fatores primos com potências maiores que 1. Logo, podemos nos restringir a primos menores ou iguais a \sqrt{n}, levando a um algoritmo O(\sqrt{n} \log(n)).

Depois dessa teoria toda, o algoritmo fica bem simples. Aqui está minha versão em C++, usando o crivo de eratóstenes para encontrar os primos.

D. A.I. War

Este problema se reduz para o seguinte problema: Dado um grafo G(V, E), encontrar o menor caminho entre s e t em um grafo não-direcionado e não-ponderado. Se houver várias soluções, escolha o caminho com maior vizinhança. Consideramos a vizinhança de um caminho como a união das vizinhanças dos vértices desse caminho, excluindo os vértices do próprio caminho. O problema pede para imprimir o comprimento desse caminho e o tamanho de sua vizinhança.

Vamos denotar por N o número de vértices nesse grafo e M o número de arestas.

Primeiramente encontramos as menores distâncias a partir de s, para todos os vértices, através de uma busca em largura. Denotamos por dist(v) a menor distância de s a v. O tamanho do menor caminho é dist(t).

Construímos então um grafo direcionado G' = (V, A), com mesmo conjunto de vértices do grafo de entrada e um arco (u, v) \in A se a dist(u) + 1 = dist(v). Podemos argumentar que todo caminho mínimo s-t no grafo original corresponde a um caminho direcionado de s a t nesse novo grafo.

Solução para o caso pequeno: podemos fazer uma força bruta a partir de s e, sempre que chegarmos em t, calculamos o tamanho da vizinhança desse caminho. Dessa forma estamos enumerando explicitamente todos os possíveis menores caminhos. Fiz uma estimativa e me pareceu que no pior caso, haverá cerca de O(\sqrt{N}^{\sqrt{N}}) caminhos. No caso fácil, P=36, o que dá uma ordem de 50k operações. No caso difícil, P=400, o que torna a abordagem inviável. De qualquer maneira, eis aqui minha solução para o caso fácil.

Solução para o caso geral: uma ideia é usar programação dinâmica para guardar o tamanho da vizinhança para um dado caminho, mas note que não basta representar um caminho por seu último vértice, pois ao adicionar um vértice a este caminho, sua contribuição para o tamanho da vizinhança pode depender de mais vértices nesse caminho.

A observação chave é que na verdade, a contribuição de um novo vértice c só depende do último e penúltimo vértice desse caminho. Para entender porque, suponha que dist(c) = D + 1 e sejam b e a o último e penúltimo vértices de um caminho, respectivamente. Então dist(b) = D e dist(a) = D-1. Se c possuísse vizinhança comum com algum vértice x tal que dist(x) \le D-2, então o menor caminho até c seria menor ou igual a D, uma contradição.

Logo, é suficiente representar um caminho por seus dois últimos vértices. Seja f(b, c) o tamanho da maior vizinhança de um caminho terminado em b \rightarrow c. Podemos definir a seguinte recorrência:

f(b, c) = \max \{ (a, b) \in A(G') | f(a, b) + g(c, a, b) \}

Aqui, g(c, a, b) é o número de vértices na vizinhança de c que não está contido nem na vizinhança de a nem na de b. O caso base é f(s, c), onde o valor é simplesmente o tamanho da união da vizinhança de s e c.

Se pré-computarmos g(c, a, b), podemos resolver a recorrência acima em O(N) e como cada par (b, c) deve pertencer a A(G'), o algoritmo tem complexidade O(NM).

Porém, calcular g(c, a, b) é a parte mais demorada. A solução mais simples seria enumerar todas as triplas de vértices e processar cada vértice v vizinhança de c, levando a um algoritmo O(N^4), o que dá na ordem de 25 \times 10^9, que é muito lento.

A sacada é usar o fato que c e v devem ser adjacentes, assim como os vértices a e b. Assim, para cada par de arestas e_1 e e_2, supomos e_1 = (c, v) e e_2 = (a, b). Usando uma matriz de adjacência, podemos verificar se v pertence à vizinhança de a e b em O(1), levando a uma complexidade total de O(M^2) ~4M operações. O editorial do Google Code Jam apresenta essa e outras 3 alternativas para pré-computar g(c, a, b). Minha implementação da solução apresentada se encontra aqui.


Defesa do Mestrado

Setembro 11, 2011

Segunda-feira passada foi a defesa da minha tese de mestrado. Felizmente correu tudo bem e fui aprovado :)

Do trabalho

O título da minha dissertação foi “Mapas de Símbolos Proporcionais”. O nome ficou bem genérico e não dá nem para saber do que se trata, hehe. Talvez fosse melhor “Problemas de otimização combinatória envolvendo mapas de símbolos proporcionais”.

Mapa de símbolos proporcionais com as maiores cidades brasileiras

De qualquer maneira, basicamente o que fizemos foi abordar dois problemas envolvendo esse tipo de mapa através de programação linear inteira, buscando soluções ótimas. Fizemos estudos teóricos mostrando que a formulação utilizada é forte, além de encontrarmos desigualdades adicionais. Também desenvolvemos técnicas de pré-processamento usando divisão-e-conquista e finalmente contribuímos com a paralelização de uma abordagem heurística.

Da banca

A banca da defesa foi composta pelo meu orientador, o prof. Pedro e pelos professores Carlinhos do IME-USP e o prof. Hélio do IC.

O prof. Carlinhos é um dos grandes responsáveis pela organização da maratona e por isso devo boa parte de minha formação a ele. O prof. Hélio foi o responsável da disciplina de estrutura de dados da qual eu fui monitor em 2010 e também foi meu professor de computação gráfica.

Ambos foram bem tranquilos na arguição, tendo apenas sugerido algumas correções ortográficas e uma melhor explicação aqui e acolá.

Da apresentação

Eu sou bastante tímido e tinha pavor de apresentar em público. Acho que os seminários do LOCo fizeram com que eu me acostumasse a apresentar, pelo menos quando se trata do meu próprio trabalho.

fonte: http://www.greenlights.org/blog/wp-content/uploads/2011/05/ostrich.jpg

Além disso, aprendi várias técnicas com meus orientadores sobre como apresentar melhor. Eis algumas delas:

  • Olhar para a platéia (esse é difícil :P)
  • Não ler os slides (além de te deixar de costas pra platéia, você não convence que sabe o conteúdo da palestra)
  • Não voltar slides. Se você sabe que vai precisar mostrar um slide que apareceu antes, duplique-o na confecção da apresentação. Se não der pra fazer isso, pelo menos avise que está voltando os slides para a plateia não ficar perdida.
  • Use “nós” ao invés de “a gente”. A vantagem é que no primeiro caso podemos usar sujeito oculto, o que torna a fala mais agradável de se ouvir.

Do aprendizado técnico

Embora eu não tenha me dado conta na hora, acho que aprendi bastante coisa no mestrado, principalmente sobre programação linear inteira e desenvolvimento de software em C++. Até então eu só tinha feito programinhas de ~100 linhas para resolver problemas de maratona, sem usar muitos conceitos de orientação de objetos.

No mestrado fiz as coisas pensando em reuso, o que acabou sendo muito bom, pois tive que utilizar código que eu havia escrito depois de um ano. O código ficou com umas 10.000 linhas.

Embora tenha usado bibliotecas como CGAL e XPRESS, se eu fosse reescrever meu código, teria usado mais bibliotecas como por exemplo a Boost.

Do futuro

Acadêmico: Há algumas tarefas possíveis para complementar o que fiz no mestrado e minha ideia é realizá-las assim que sobrar um tempinho. Mesmo não tendo certeza se voltarei para um doutorado, eu gosto bastante de publicar :) e isso me motiva a continuar pesquisando.

Profissional: Pesquisa em áreas como geometria computacional é rara de ser encontrada fora da academia, pelo menos no Brasil. Eu ia fazer meu mestrado em geometria, mas meu orientador sugeriu um problema que no final das contas usou bastante otimização combinatória e eu sou grato pelo rumo que as coisas tomaram. Graças a isso estou trabalhando em uma empresa de pesquisa operacional. Otimização em geral é uma área com aplicação direta na indústria e por isso é possível encontrar algumas empresas do ramo no Brasil.


Sibgrapi 2011

Setembro 4, 2011

Nessa última semana aconteceu o Sibgrapi 2011, que é uma conferência brasileira de abrangência internacional de computação gráfica, padrões e imagens. O evento foi sediado em Maceió, Alagoas. Tivemos um artigo aceito para essa conferência e fui lá apresentar.

O Sibgrapi deste ano foi composto por diversos mini-cursos, palestras de pesquisadores de renome na área, apresentações orais dos artigos (em inglês) e apresentação de pôsteres (artigos e também teses de iniciação/mestrado/doutorado).

Mini-cursos

Acho que a parte mais interessante de conferências são os minicursos. Nessa edição do Sibgrapi, cada mini-curso foi dividido em duas partes.

Houve um particularmente interessante, sobre fotografia computacional, onde eles explicaram alguns conceitos básicos sobre ótica e fotografia e falaram dos principais temas dessa área.


Imagens com diferentes tempos de exposição (fonte)

Foram discutidas diversas técnicas de composição de imagens. A mais legal pra mim, sem dúvida é a do high dynamic range (HDR), que consiste em usar imagens com diferentes tempos de exposição (como no exemplo da figura acima) para compor uma imagem visualmente mais atraente (como no exemplo da figura abaixo). Outros exemplos impressionantes podem ser encontrados nesse site.


Imagem composta (fonte)

Falaram também sobre light fields, que pelo que entendi consiste em representar mais informação a partir de um dado ponto de vista. Um exemplo disso é essa câmera que tira fotos com diferentes focos que podem ser escolhidos depois, na própria imagem. Veja exemplos aqui.

Assisti também a um tutorial sobre OpenCV, mas só peguei a primeira parte, pois a segunda conflitava com o horário do tutorial sobre fotografia computacional.

Apresentação de artigos técnicos

Havia sempre duas seções paralelas de apresentações de artigos técnicos, o que impossibilitou assistir a todas elas. Pelo que pude perceber, uma linha era voltada à computação gráfica e a outra à processamento de imagens. Acabei escolhendo apenas seções de computação gráfica.

Pra dizer a verdade, entendi muito pouco dos trabalhos apresentados, mas os que mais me chamaram a atenção foram de modelagem de terrenos em tempo real usando CPU-GPU (link) e texturização de modelos 3D com poucas características geométricas (link).

Apresentei nosso trabalho em uma seção de visualização. Trata-se de uma solução para uma das variantes do problema de mapas de símbolos proporcionais que abordei no meu mestrado (link). Pretendo comentá-la em um post futuro.

Pôsteres de teses

O projeto mais interessante era a tese de mestrado de Adriana Schulz (IMPA) que estudou animação computadorizada, mais especificamente para simulação de coreografia. Esse site tem diversos vídeos bacanas!

Fato curioso

Embora os artigos tivessem que ser apresentados em inglês, os mini-cursos foram ministrados em português. Além disso, as palestras dadas por convidados brasileiros também estavam sendo dadas em português. Aí houve uma hora em que na seção de dúvidas, um cara fez a pergunta em alemão. Depois de todo mundo ficar com cara de pastel, ele repetiu em inglês, criticando o fato de uma palestra de conferência de nível internacional ter sido dada em português. A partir de então, só tivemos palestras em inglês :)

Turismo

Aproveitei minha ida a Maceió para conhecer alguns pontos turísticos de Alagoas. A cidade de Maceió em particular tem uma boa estrutura para turismo, com empresas de transporte e serviço de guias. Consegui visitar a praia do Gunga, onde existem falésias compostas de camadas coloridas.


Camadas coloridas das falésias

Também fui a Maragogi, famosa por suas piscinas naturais, onde se pode mergulhar em meio a peixes coloridos e corais.


Piscina natural em Maragogi

Conclusão

Foi a primeira vez que apresentei em inglês e para um público desconhecido. Acredito ter sido um bom ensaio para a minha defesa que ocorrerá logo mais.

Os passeios nos últimos dias também serviram como um descanso relâmpago, pois esses últimos três meses têm sido bem puxados :)