Haskell – Tipos de Dados Algébricos

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.