Tipos de Dados Algébricos

Veja a playlist no Youtube com todos os vídeos do curso.

1 Além dos tipos padrões

Os tipos padrões são suficientes para construírmos nossos programas e inferirmos alguns fatos sobre as funções que estamos implementando. Por exemplo, considerando a seguinte assinatura de função, temos um número limitado de operações que podemos efetuar:

f :: Int -> Int

Sabendo que a entrada e saída dessa função são valores do tipo Int, podemos somar um valor a entrada, ou talvez multiplicar esse valor por uma constante:

f :: Int -> Int
f x = x + 1

g :: Int -> Int
g x = x * 2

Além das operações óbvias que podemos fazer com um inteiro, podemos também gerar transformações intermediárias nesse tipo, contanto que o resultado final seja um Int.

f :: Int -> Int
f = length . show

Ou seja, o conjunto de operações permitidas dentro de uma função pode se estender caso tenhamos funções intermediárias de conversão de tipos.

Quando falamos em desenvolvimento guiado por tipos, a assinatura da função deve restringir ao máximo o conjunto de operações que podemos aplicar internamente e que façam sentido ao contexto.

No nosso exemplo acima, o que esse inteiro representa? É uma moeda? Altura de uma pessoa em centímetros? Temperatura atual? Dependendo do contexto, o conjunto de operações pode variar. Faze sentido multiplicarmos duas alturas? Saber quantos dígitos tem a quantidade de dinheiro que você possui?

Para isso, precisamos que a linguagem permita envolver os tipos de entrada e saída da função dentro de um contexto. Uma forma de fazer isso é criando apelidos para tipos.

1.1 Apelidando os tipos

Para apelidar os tipos em Haskell utilizamos a palavra-chave type seguida do apelido que queremos dar e o tipo que estamos apelidando separados pelo sinal de igualdade =:

type Money = Int

withdraw :: Money -> Money -> Money
withdraw account qty
  | account < qty = error "Are you trying to rob a bank?"
  | otherwise     = account - qty

Sabendo que os inteiros representam moedas, podemos pensar um pouco mais sobre o que podemos e devemos fazer na implementação da função. Por exemplo, sabemos que o saldo na conta não pode ficar negativo e, com isso, criamos um caso de exceção. Note que com isso, a função se tornou parcial e, ao ser utilizada de forma incorreta, emite um erro em tempo de execução. Em breve veremos como transformar tais funções em totais.

Um ponto problemático de type é que ele cria apenas um apelido para um tipo (à la typedef em C). Para todos os efeitos, todo valor do tipo Money é simplesmente um Int e todo valor do tipo Int pode ser utilizado como Money. Portanto, isso aqui é válido:

type Money       = Int
type Temperature = Int

x = -3 :: Temperature
y = withdraw x 4

Mesmo que x seja do tipo incorreto, ele é aceito durante a compilação pois, ao compilar o código, todos os tipos definidos por type são substituídos pelos tipos correspondentes em uma etapa de pré-processamento.

O que precisamos para tornar nosso código mais seguro é criar novos tipos que são completamente distintos dos tipos já existentes.

1.2 Criando um novo tipo

Podemos criar um novo tipo que possui uma interpretação diferente de um Int utilizando a palavra-chave newtype:

newtype Money = MkMoney Int

withdraw :: Money -> Money -> Money
withdraw (MkMoney account) (MkMoney qty)
  | account < qty = error "Are you trying to rob a bank?"
  | otherwise     = MkMoney (account - qty)

Agora temos um tipo Money que é um tipo completamente diferente dos tipos que temos disponíveis. Esse tipo simplesmente armazena um valor do tipo Int. Esse valor está encapsulado dentro de uma caixa definida pelo construtor MkMoney.

Um construtor de valores de um tipo pode ser visto como uma função que recebe um valor do que ele irá conter e devolve um valor do tipo desejado. E, de fato, ao consultarmos o tipo de MkMoney no ghci, obtemos:

> :t MkMoney
MkMoney :: Int -> Money

Podemos ler da seguinte maneira: “se você me der um valor do tipo Int, eu te devolvo um valor do tipo Money que contém esse inteiro.

A criação desse novo tipo cria um inconveniente pois precisamos implementar todas as operações fundamentais necessárias ou conviver com o uso do pattern matching na definição das funções. Por exemplo, podemos definir uma instância de Num para esse novo tipo:

newtype Money = MkMoney Int

instance Num Money where
  (MkMoney x) + (MkMoney y) = MkMoney (x + y)
  (MkMoney x) - (MkMoney y) = MkMoney (x - y)
  (MkMoney x) * (MkMoney y) = MkMoney (x * y)
  negate (MkMoney x)        = MkMoney (negate x)
  abs (MkMoney x)           = MkMoney (abs x)
  signum (MkMoney x)        = MkMoney (signum x)
  fromInteger x             = MkMoney x

Com isso nossa função withdraw se torna:

newtype Money = MkMoney Int

withdraw :: Money -> Money -> Money
withdraw account qty
  | account < qty = error "Are you trying to rob a bank?"
  | otherwise     = account - qty

Porém, esse é um padrão tão comum que o compilador consegue criar essas instâncias automaticamente.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
newtype Money = MkMoney Int
  deriving (Read, Show, Num)

Com a extensão GeneralizedNewtypeDeriving podemos derivar automaticamente as instâncias de Read, Show, Num dentre outras para nosso tipos criados por newtype. O compilador infere para a gente as operações numéricas! Para mais informações consulte a documentação do GHC.

Essa derivação automática reflete um pouco a quantidade de informação contida em um tipo. Por saber exatamente o tipo que ele carrega e as operações fundamentais, o compilador desenvolve (== gera código automaticamente) diversas funcionalidades sem intervenção do desenvolvedor.

Retomando nosso exemplo original, se implementarmos o seguinte código o compilador vai retornar uma mensagem de erro:

x = -3 :: Int
y = withdraw x (MkMoney 5) -- erro de compilação

Agora, o tipo de x não é o mesmo que o tipo esperado pela função withdraw, não podemos misturar valores de natureza diferente. Ainda assim, podemos fazer algo como withdraw (fromInteger x) (MkMoney 5) e o compilador aceitará. Veremos algumas estratégias para evitar essa situação mais adiante.

1.3 Tipos Compostos

Em algumas situações queremos que nossos tipo contenham múltiplos valores do mesmo ou de diferentes tipos. Por exemplo, considerem que você quer representar sua conta no banco com um valor na sua conta corrente e outro em um determinado investimento:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
newtype Money = MkMoney Int
  deriving (Read, Show, Num)

newtype Account = MkAccount (Money, Money)

Para juntar essa informação você pode utilizar o tipo tupla. Porém, com essa definição nosso código não possui uma semântica clara: qual dos dois valores do tipo Money representa a conta corrente? Se quisermos incluir um novo campo para indicar dívidas com o banco e acrescentarmos uma String junto da informação de investimento, o nosso tipo passa a ser:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
newtype Money = MkMoney Int
  deriving (Read, Show, Num)

newtype Account = MkAccount ((Money, (String, Money)), Money)

A cada novo campos que acrescentamos, maior será o aninhamento de tuplas. Isso faz com que nosso código fique cada vez mais difícil de manter. Além disso cada um dos tipos Money podem permitir um conjunto diferente de operações. Por exemplo, você pode depositar e sacar da sua conta, mas só pode pagar sua dívida.

1.4 Tipos Paramétricos

Um outro aspecto importante, tanto da definição dos tipos, como das funções é a parametricidade. Um tipo paramétrico é criado de tal forma que parte de sua informação será definida posteriomente, dependendo do contexto da aplicação.

Digamos que queremos criar um tipo que armazena uma lista da frequência observada de cada um dos valores de um certo tipo. A contagem é representada pelo tipo Int, o tipo que queremos contar deve ficar em aberto para definirmos durante a aplicação:

newtype Counter a = MkCounter [(a, Int)]

O tipo Counter armazena uma lista de tuplas de um tipo a (seja ele qual for), junto de um Int, representando quantas vezes observamos dado valor de a. Nessa sintaxe, o a representa um parâmetro ou variável de tipo . Em outras palavras, deixamos em aberto o tipo que Counter carregará.

countWords :: Counter String
countWords = MkCounter [("Oi", 10), ("Olá", 15), ("Mundo", 25)]

evidences :: Counter Bool
evidences = MkCounter [(False, 10), (True, 15)]

Quando o tipo possui um parâmetro de tipo, dizemos que ele é um Tipo de Dados Abstrato , pois certos detalhes de sua definição estão escondidos. Podemos implementar funções que recebem versões específicas desse tipo ou funções abstratas que também deixam a definição em aberto:

checkFacts :: Counter Bool -> Double
checkFacts counts = trues / falses
  where
    trues  = fromIntegral $ filterAndGroup id  counts
    falses = fromIntegral $ filterAndGroup not counts

filterAndGroup :: (a -> Bool) -> Counter a -> Int
filterAndGroup p (MkCounter xs) = foldr countIf 0 xs
  where
    countIf (x, c) acc
      | p x       = c + acc
      | otherwise = acc

A função checkFacts aceita apenas valores do tipo Counter Bool e, como consequência, a função que é passada como argumento de filterAndGroup dentro dessa implementação deve ser do tipo Bool -> Bool. O contexto dessa função restringe as outras funções utilizadas dentro dela.

Já a função filterAndGroup aceita o tipo Counter a para qualquer a. Para tanto, um dos argumentos deve ser uma função que recebe exatamente esse tipo a e devolve um Bool.

É tentador imaginar que uma função genérica que recebe um tipo a é mais flexível em sua implementação. Porém, veremos mais adiante que, na verdade, ela restringe o conjunto de implementações possíveis.

Tipos mais interessantes podem ser criados como uma composição de tipos fundamentais, conforme veremos em seguida.

2 Tipos de Dados Algébricos

Vimos anteriormente que podemos utilizar o newtype para criar novos tipos de dados e, com certas limitações, tipos compostos. Tanto no Haskell como em muitas linguagens modernas, podemos criar novos tipos com maior flexibilidade utilizando os Tipos de Dados Algébricos .

A ideia dos Tipos de Dados Algébricos, ou ADTs (Algebraic Data Types), é que podemos construir novos tipos utilizando operações algébricas de soma e produto.

Os tipos internos da linguagem e os novos tipos criados servem como operandos dos tipos algébricos. Como veremos mais adiante, as operações algébricas dos ADTs também possuem algumas das propriedades observadas na aritmética, para isso, temos dois tipos fundamentais que representam os valores \(0\) e \(1\).

data Void

data () = ()

A definição de um novo tipo é feita com a palavra-chave data. A sintaxe completa é data Nome-do-tipo = Valores. Tanto o nome do tipo, como seus valores devem iniciar em letras maiúsculas (exceto quando usamos símbolos).

Dos tipos definidos acima, Void é um tipo que não contém valor nenhum e, portanto, não podemos tentar avaliar um valor desse tipo. Apesar dessa limitação, esse tipo pode nos ajudar a guiar o desenvolvimento de nossas aplicações, como veremos em breve.

O tipo (), também conhecido como unitário (en: unit), possui apenas um único valor (()). Inicialmente esse tipo parece muito chato e previsível, pois sempre que observamos um valor desse tipo, ele será o mesmo. Porém, assim como o Void, ele também será de grande ajuda no desenvolvimento guiado por tipos, talvez com outros nomes.

Tendo definido os tipos fundamentais, vamos aprender em seguida os tipos produto e soma.

2.1 Tipo Produto

O Tipo Produto compõe dois ou mais tipos criando um novo tipo que carrega informação de todos eles. Em Haskell, um Tipo Produto é definido pela sintaxe

data Nome = Construtor Tipo1 Tipo2 .. TipoN

Esse tipo é análogo ao struct da linguagem C e C++:

struct Nome {
  Tipo1 x;
  Tipo2 y;
  ...
  TipoN z;
}

Vamos exemplificar criando um tipo que contém um Bool indicando se um usuário é admin, uma String com o nome do usuário e uma função que recebe um Int representando o número de uma sala, acessa um banco de dados e devolve um Int representando um PIN Code para ser utilizado naquela porta.

data User = MkUser Bool String (Int -> IO Int)

Contrastando com o uso de newtype e tuplas, essa sintaxe é bem melhor. Porém, podemos deixar mais clara a intenção de cada campo usando a sintaxe para registros record syntax :

data User = MkUser { _isAdmin  :: Bool
		   , _username :: String
		   , _openDoor :: Int -> IO Int
		   }

Essa sintaxe se assemelha ainda mais ao struct de C e NamedTuples de Python. Os nomes dos campos são funções criadas automaticamente em tempo de compilação que recupera o respectivo campo. Por convenção os nomes dessas funções começam com underline. Com isso podemos fazer:

openSecretDoor :: User -> IO Int
openSecretDoor user
  | _isAdmin user = getSecretPIN
  | otherwise     = print "Nice try, Mr. Robot!" >> pure 0

O objetivo dessa função é permitir que um usuário com permissão de admin possa abrir uma porta secreta, ou seja, ao chamar essa função para um usuário que tenha a permissão correta, ela deve retornar o código PIN para abertura da porta. Caso contrário, imprimimos uma mensagem de erro e retornamos um código \(0\).

Está claro através do nome da função e de seu tipo o que desejamos implementar. Ainda assim, o desenvolvedor pode esquecer de verificar se o usuário tem permissão ou inverter a verificação, levando a um código incorreto e inseguro. Será que conseguimos restringir ainda mais essa função?

Antes de respondermos essa pergunta, vamos verificar o quanto de informação o tipo produto traz para nossas implementações.

2.2 Segurança do Tipo Produto

Ao criar uma biblioteca que define uma nova estrutura do tipo produto junto com algumas operações, você restringe as implementações possíveis de funções que recebem ou devolvem esse tipo.

Considere a função openSecretDoor definida acima. Ao receber um argumento do tipo User, em primeiro momento você está limitado a aplicar apenas três funções: _isAdmin, _username, _openDoor. A partir desse ponto, sua função pode aplicar qualquer função que aceite como entrada os tipos de retorno de uma dessas três funções. Ainda assim temos bastante opções de implementação…

Um outro ponto a ser considerado é que pode não ser interessante permitir que o usuário de sua biblioteca possa criar um valor desse tipo, imagine que seja possível fazer o seguinte no código dele:

hackTheSystem :: User
hackTheSystem = MkUser True "mrRobot" (pure 42)

Ele teria como acessar a informação para abrir a porta secreta…

Uma forma de melhorar a segurança é limitar o que estará exposto ao usuário de sua biblioteca:

module Users
   ( createNewUser
   , getYourUser
   , openSecretDoor
   , openDoor
   ) where

 getYourUser :: String -> String -> IO User
 getYourUser username password = do
    db   <- openDB
    user <- queryDB db username password
    closeDB db
    return user

 createNewUser :: User -> Bool -> String -> (Int -> IO Int) -> IO ()
 createNewUsere user isAdm username opendoors
   | _isAdmin user = openDB >>= createUser isAdm username opendoors >>= closeDB
   | otherwise     = print "ACCESS DENIED! TERMINATE!"

 openSecretDoor :: User -> IO Int
 ...

 openDoor :: User -> Int -> IO Int
 openDoor = _openDoor

Dessa forma o usuário dessa biblioteca só terá disponível para uso essas quatro funções. Com isso, ele não consegue criar um novo usuário exceto se ele for admin. Como bônus, limitamos ainda mais as operações que podemos fazer com uma função que recebe ou retorna valores do tipo User. Imagine uma função com a seguinte assinatura:

funcao :: User -> User

Quais são as implementações possíveis?

funcao :: User -> User
funcao = id

E a seguinte função?

funcao :: User -> IO String

Essa permite algumas implementações extras:

funcao :: User -> IO String
funcao user = do
  pass <- openSecretDoor
  pure (show pass)

funcao :: User -> IO String
funcao user = do
  passwords <- mapM (openDoor user) [0 .. 1000]
  pure (concatMap ((++",") . show) passwords )

Além dessas implementações temos uma variedade de outras possibilidades. Imagine que, ao converter um Int para String, podemos fazer todas as implementações de uma função String -> IO String. De todo modo, o contexto da aplicação nos permite limitar essas possibilidades. Certamente a implementação correta não é aplicar o valor 0 repetidamente na função openDoor. Caso a funcao tenha um nome específico da tarefa que queremos executar, a intuição do que queremos implementar se torna ainda mais clara.

2.3 Tipo Soma

O Tipo Soma permite você enumerar os possíveis valores de um tipo. Essa definição de tipo é similar ao enum do C, porém mais seguro e flexível. Para criar um tipo soma, definimos os valores separados por |:

data Nome = Valor1 | Valor2 | ... | ValorN

Em C, isso é equivalente a

enum Nome{ Valor1, Valor2, ... ValorN };

Só que, diferente da linguagem C, os nomes Valor1, Valor2, ... não são apenas apelidos para uma sequência de int. Eles são valores únicos e bem definidos.

Continuando com nossos exemplos, podemos criar um tipo que descreve o estado atual da porta que queremos abrir.

data Door = Open | Closed
	       deriving Eq

Notem que Open, Closed são valores do tipo Door e não podemos fazer nada com eles além de checar se dois valores desse tipo são iguais. Com isso podemos alterar nossa função de abrir portas para:

openDoor :: User -> Int -> IO Int
openDoor user door =
  case doorStatus door
    Open   -> print "You don't need a code!" >> pure 0
    Closed -> _openDoor user door

Note que caso a porta esteja aberta, estamos retornando o código \(0\) por padrão. Podemos criar um tipo soma que define um valor padrão nulo ou ausente.

data Optional a = None | Some a

openDoor :: User -> Int -> IO (Optional Int)
openDoor user door =
  case doorStatus door
    Open -> print "You don't need a code!" >> pure None
    Closed -> Some <$> _openDoor user door

Agora, caso não seja necessário retornar um código de abertura, podemos retornar None, indicando que nada foi retornado. Na verdade, esse tipo já existe no Haskell com outro nome:

data Maybe a = Nothing | Just a

Note que esse é um tipo paramétrico que possui mais do que dois valores: um valor é Nothing, indicando ausência de informação e, os outros valores, é a enumeração de todos os valores representáveis pelo tipo a.

Para tornar nosso exemplo mais interessante, vamos criar um novo tipo chamado Breach, indicando possíveis problemas de segurança com a porta, e vamos parametrizar nosso tipo Door:

data Door a = Closed | Open | Breached a
		deriving Eq
data Breach = Hacked | Broken | NoEnergy
		deriving Eq

openDoor :: User -> Int -> IO (Optional Int)
openDoor user door =
  case doorStatus door
    Open            -> print "You don't need a code!" >> pure None
    Closed          -> Some <$> _openDoor user door
    Breached breach -> print "Door has been breached! Warn security!"
			 >> printInstructions breach
			 >> pure None

A decisão de deixar o valor Breached com um parâmetro de tipo é de tal forma a permitir uma flexibilidade de seu uso. Por exemplo, se temos um valor do tipo Breached Breach e, eventualmente, queremos transformar tal valor para um tipo Breached String, permitindo a leitura das instruções por um usuário, basta fazer (dado que implementamos uma instância de Functor para esse tipo):

fromBreachToStr :: Door Breach -> Door String
fromBreachToStr = fmap b2s
 where
   b2s Hacked   = "you've been hacked!"
   b2s Broken   = "the door has been forced and broken!"
   b2s NoEnergy = "we lost energy, guard the door!"

No desenvolvimento guiado por tipos, os tipos soma costumam limitar o tipo de operações que são possíveis de serem implementadas. Por exemplo, considere a função:

funcao :: Door Breach -> Door Breach

Como podemos implementar essa função? O primeiro passo é dividir os casos de valores possíveis para o tipo Door Breach:

funcao :: Door Breach -> Door Breach
funcao Closed              =
funcao Open                =
funcao (Breached Hacked)   =
funcao (Breached Broken)   =
funcao (Breached NoEnergy) =

Em seguida, temos que, para cada entrada, escrever a saída correspondente. Para cada um dos \(5\) casos de entrada, temos \(5\) possibilidades de saídas. Ou seja, dada essa entrada e saída, temos \(5^5 = 3125\) implementações diferentes.

Embora os tipos estejam limitando as possíveis implementações, ainda assim temos um número muito grande. Quando especificamos um nome para a função que descreve seu objetivo, podemos reduzir intuitivamente a quantidade de possibilidades. Por exemplo, uma função chamada de closeDoor, dificilmenete vai gerar uma saída com valor Open.

Caso o parâmetro de tipo de Door não esteja especificado, reduzimos ainda mais as possibilidade:

funcao :: Door a -> Door a
funcao Closed       =
funcao Open         =
funcao (Breached x) =

Uma vez que essa função deve ser implementada para qualquer tipo a, temos agora \(3^3 = 27\) possíveis implementações. Novamente, precisamos de mais informações sobre o objetivo da função para determinar a implementação correta.

2.4 Combinando Tipos Soma e Produto

É possível combinar os tipos soma e produto na definição de um novo tipo. Por exemplo, poderíamos criar uma nova definição do tipo representando usuário como:

data User = Admin { _openDoor :: Int -> IO Int }
	  | User  { _username :: String
		  , _openDoor :: Int -> IO Int
		  }

Agora, com essa nova definição, temos dois valores completamente distintos para o usuário admin e para usuários normais. Nosso código de manipulação de usuários se torna:

module Users
   ( createNewUser
   , getYourUser
   , openSecretDoor
   , openDoor
   ) where

 getYourUser :: String -> String -> IO User
 getYourUser username password = do
    db   <- openDB
    user <- queryDB db username password
    closeDB db
    return user

 createNewUser :: User -> Bool -> String -> (Int -> IO Int) -> IO ()
 createNewUser (Admin _) isAdm username opendoors =
    openDB >>= createUser isAdm username opendoors >>= closeDB
 createNewUser _  = print "ACCESS DENIED! TERMINATE!"

 openSecretDoor :: User -> IO (Maybe Int)
 openSecretDoor (Admin _) = pure $ Just 1234
 openSecretDoor _         = print "DENIED!" >> pure Nothing

 openDoor :: User -> Int -> IO Int
 openDoor = _openDoor

Uma vez que a diferença entre um admin e um usuário normal não depende de um atributo booleano, é impossível injetar essa informação de qualquer forma em um usuário normal. Fica mais difícil na implementação você atribuir um poder extra para um usuário normal por não fazer a verificação _isAdmin ou inverter a lógica.

  1. Either: o tipo soma padrão

    No Haskell temos um tipo que representa a soma canônica:

    data Either a b = Left a | Right b

    Um tipo canônico significa que pode ser utilizado para construir qualquer tipo soma. Por exemplo, nosso tipo User pode ser reescrito como:

    data User = Admin { _openDoor :: Int -> IO Int }
	  | User  { _username :: String
		  , _openDoor :: Int -> IO Int
		  }
type EitherUser = Either (Int -> IO Int) (String, Int -> IO Int)

    Para todos os efeitos eles contém a mesma informação, apenas estruturada de forma diferente.

2.5 Tipo Recursivo

Embora os tipos soma e produtos sejam suficientes para implementar muitas das estruturas comuns em diversas aplicações, elas são insuficientes para criação de estruturas lineares e não-lineares. Por exemplo, como implementar uma lista ligada utilizando apenas tais recursos?

Para implementar tais tipos, podemos definir um novo tipo em função dele mesmo. Por exemplo, uma lista ligada é definida como1:

data [a] = [] | a : [a]

Ou seja, ou o valor dela é uma lista vazia ou ela contém um elemento (cabeça) e um restante de lista (cauda). Como em Haskell trabalhamos com avaliação preguiçosa, não importa se existe um valor terminal. Podemos definir um tipo de stream infinito de dados como:

data Stream a = a |> Stream a

Nesse caso, o Stream é composto por um elemento e uma outra Stream, não existe final para essa estrutura (e tudo bem, contanto que não seja requisitado o elemento final!).

  1. Árvore Binária

    Um outro exemplo de estrutura recursiva é a Árvore Binária que pode ser definida como:

    data Tree a = Empty | Node (Tree a) a (Tree a)

    Essa estrutura permite criar uma diversidade de árvores binárias, como por exemplo:

    Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty)

    Que é desenhada como:

    A única garantia que essa definição nos dá é que um nó folha não guarda qualquer informação sobre o tipo a, valores do tipo a estão apenas nos nós internos. Podemos desenhar árvores balanceadas, como o exemplo acima, ou árvores que pendem para um dos lados. A árvore pode ser uma árvore de busca se assim quisermos, mas nada na estrutura garante essa propriedade.

    Considere o seguinte código:

    insert_balanced :: a -> Tree a -> Tree a
insert_balanced x Empty = Node Empty x Empty
insert_balanced x (Node l y r)
  | height l > height r = Node l y (insert_balanced x r)
  | otherwise           = Node (insert_balanced x l) y r

    Não existe nada na estrutura que nos impeça de inserir o novo elemento no ramo errado e causar um desbalanceamento. Uma simples troca no operador de comparação faz com que nossa implementação fique incorreta. E se eu entregar esse código no meu trabalho? E se o código for público e as pessoas perceberem meu erro? E se eu ficar conhecido como o Bug Builder?

    Existe uma forma de garantir que nossa árvore sempre será balanceada (não confundir o nome da estrutura abaixo com a estrutura B-Tree):

    data BTree a = BEmpty | BNode a (BTree (a, a))

    Note que essa estrutura é similar a lista ligada, porém, a cada recursão eu dobro a quantidade de elementos que ela carrega. Por exemplo, a árvore do exemplo anterior seria representada como:

    btree = BNode 2 (BNode (1,3) BEmpty)

    Por definição, cada nível \(n\) dessa árvore possui \(2^n\) nós, fazendo com que ela seja uma árvore perfeitamente balanceada. Porém, ela exige que cada nível esteja completo. Não podemos inserir uma lista de valores \([1,2,3,4]\) nessa árvore (tente!).

    A inserção de elemento fica:

    insert_balanced2 x BEmpty       = BNode x BEmpty
insert_balanced2 x (BNode y ys) = BNode y $ insert_balanced2 x ys

    Isso não compila! Mas, qual o problema? Tente definir a assinatura dessa função.

    No primeiro caso de entrada a assinatura deveria ser a -> BTree b -> BTree a, no segundo caso seria a -> BTree b -> BTree b. A única diferença está na saída da função que pode ser um entre dois tipos, podemos utilizar o tipo soma canônico Either para representar a saída:

    insert_balanced2 :: a -> BTree b -> Either (BTree a) (BTree b)
insert_balanced2 x BEmpty       = Left BNode x BEmpty
insert_balanced2 x (BNode y ys) = BNode y $ insert_balanced2 x ys

    O primeiro caso está correto e de acordo com a assinatura. Para o segundo caso, temos que retornar um Right (BTree b). Como fazer isso? Tente por alguns instantes.

    Não temos como implementar essa função com o que temos agora. Como alternativa, podemos implementar uma função que cria uma árvore dado que você providencie um elemento e duas árvores representando os ramos da esquerda e direita:

    insertB :: a -> BTree a -> BTree a -> BTree a
insertB x l r = BNode x (merge l r)
  where
    merge :: BTree a -> BTree a -> BTree (a, a)
    merge BEmpty       BEmpty       = BEmpty
    merge (BNode y ty) (BNode z tz) = BNode (y,z) $ merge ty tz

    Note que a nossa estrutura garante que as árvores esquerda e direita possuem a mesma quantidade de elementos. Com isso, podemos criar nossa árvore exemplo como:

    bnode1 = insertB 1 BEmpty BEmpty
bnode3 = insertB 3 BEmpty BEmpty
bnode2 = insertB 2 bnode1 bnode3

  1. Árvore de Expressão

    Vamos agora apresentar um outro tipo de árvore que pode ter um número variado de filhos dependendo do tipo do nó (embora inicialmente teremos apenas os casos com dois filhos). Essa árvore vai representar uma expressão matemática composta de operadores binários, ternários, funções univariadas, e constantes.

    data Expr = Const Int
	  | Add Expr Expr
	  | Mul Expr Expr

    Vamos implementar uma função que avalia uma expressão para um inteiro. Faremos passo a passo com a ajuda da informação desse tipo:

    evalExpr :: Expr -> Int
evalExpr _ = _

    O primeiro passo é expandir os padrões de entrada:

    evalExpr :: Expr -> Int
evalExpr (Const x) = _
evalExpr (Add l r) = _
evalExpr (Mul l r) = _

    No primeiro padrão temos um valor \(x\) do tipo Int envolvido no construtor Const. Como queremos retornar um Int e esse construtor representa um valor constante, podemos retornar o próprio x.

    evalExpr :: Expr -> Int
evalExpr (Const x) = x
evalExpr (Add l r) = _
evalExpr (Mul l r) = _

    No segundo padrão temos o construtor Add contendo dois valores do tipo Expr. A ideia é que a gente converta esses valores para Int de alguma forma e some o resultado. Bom, a única função que temos disponível para converter um Expr para Int é a própria evalExpr!

    evalExpr :: Expr -> Int
evalExpr (Const x) = x
evalExpr (Add l r) = evalExpr l + evalExpr r
evalExpr (Mul l r) = _

    O último padrão é análogo só que efetuando multiplicação.

    evalExpr :: Expr -> Int
evalExpr (Const x) = x
evalExpr (Add l r) = evalExpr l + evalExpr r
evalExpr (Mul l r) = evalExpr l * evalExpr r

    Digamos que queremos introduzir outros tipos de nós que armazenam um valor booleano e acrescentar operações entre booleanos.

    data Expr = IConst Int
	  | BConst Bool
	  | Add Expr Expr
	  | Mul Expr Expr
	  | And Expr Expr
	  | Or  Expr Expr

    Com essa mudança, nosso evalExpr se torna:

    evalExpr :: Expr -> Int
evalExpr (IConst x) = x
evalExpr (BConst x) = x
evalExpr (Add l r)  = evalExpr l + evalExpr r
evalExpr (Mul l r)  = evalExpr l * evalExpr r
evalExpr (And l r)  = evalExpr l && evalExpr r
evalExpr (Or l r)   = evalExpr l || evalExpr r

    E…o compilador explode com uma mensagem de erro. Note que o valor retornado por nossa função deve ser um Int, mas nossa árvore pode terminar com um Bool. Nesse caso, nosso evalExpr pode retornar ou um inteiro ou um booleano:

    evalExpr :: Expr -> Either Int Bool
evalExpr (IConst x) = Left x
evalExpr (BConst x) = Right x
evalExpr (Add l r)  = case evalExpr l of
			Left x -> case evalExpr r of
				    Left y -> x + y
				    Right _ -> error "invalid expression"
			Right _ -> error "invalid expression"
evalExpr (Mul l r)  = case evalExpr l of
			Left x -> case evalExpr r of
				    Left y -> x * y
				    Right _ -> error "invalid expression"
			Right _ -> error "invalid expression"
evalExpr (And l r)  = case evalExpr l of
			Right x -> case evalExpr r of
				    Right y -> x && y
				    Left _ -> error "invalid expression"
			Left _ -> error "invalid expression"
evalExpr (Or l r)  = case evalExpr l of
			Right x -> case evalExpr r of
				    Right y -> x || y
				    Left _ -> error "invalid expression"
			Left _ -> error "invalid expression"

    E o código agora ficou muito mais complicado…mas ele vai nos avisar se tentarmos combinar booleanos com inteiros. E se fosse possível extrair a informação de qual tipo a árvore está carregando?

3 Tipo Fantasma 👻

Um truque para tentar organizar essa bagunça é modificar nosso tipo para que ele seja paramétrico e o parâmetro do tipo irá nos indicar que tipo de expressão estamos avaliando.

data Expr a = IConst Int
	    | BConst Bool
	    | Add (Expr a) (Expr a)
	    | Mul (Expr a) (Expr a)
	    | And (Expr a) (Expr a)
	    | Or  (Expr a) (Expr a)

Agora podemos criar um Expr Int para indicar que nossa expressão avalia para inteiro. Mas peraí…o parâmetro a não é utilizado em momento algum na definição do nosso tipo. Na verdade, esse parâmetro serve apenas para rotular nosso tipo. Isso é conhecido como tipo fantasma (pois o valor do tipo a não existe).

Agora podemos criar um avaliador para inteiros e outro para booleanos:

evalInt :: Expr Int -> Int
evalInt (IConst x) = x
evalInt (Add l r)  = evalInt l + evalInt r
evalInt (Mul l r)  = evalInt l * evalInt r
evalInt _          = undefined

evalBool :: Expr Bool -> Bool
evalBool (BConst x) = x
evalBool (And l r)  = evalBool l && evalBool r
evalBool (Or l r)   = evalBool l || evalBool r
evalBool _          = undefined

Porém, nada nos impede de fazer algo como:

fakeExpr = BConst True :: Expr Int

Não existe nenhuma instrução para o compilador de que isso é uma construção inválida!

Para minimizar esse problema, precisamos esconder os construtores do usuário (já fizemos isso com o tipo User) e exportar apenas construtores que garantam uma expressão bem formada.

fromInt :: Int -> Expr Int
fromInt = IConst

(.+.) :: Expr Int -> Expr Int -> Expr Int
(.+.) = Add

(.*.) :: Expr Int -> Expr Int -> Expr Int
(.*.) = Mul

fromBool :: Bool -> Expr Bool
fromBool = BConst

(.&.) :: Expr Bool -> Expr Bool -> Expr Bool
(.&.) = And

(.|.) :: Expr Bool -> Expr Bool -> Expr Bool
(.|.) = Or

treeA = fromInt 1 .+. fromInt 2
treeB = fromInt 1 .|. fromBool True -- não compila

3.1 Tipo User com Fantasmas

Relembrando o tipo User, podemos eliminar a soma de tipos fazendo:

data User a = User { _username :: String
		   , _openDoor :: Int -> IO Int
		   }

E para identificar se um usuário é admin, criamos dois tipos vazios (nós tínhamos prometido mostrar que eles eram úteis, não tínhamos? 😜):

data Noob
data Admin

Veja que esses tipos são iguais ao tipo Void, não possuem valores válidos associados a eles. Mas tudo bem, não precisaremos de valores da forma que utilizaremos esses tipos:

module Users
   ( createNewUser
   , getYourUser
   , openSecretDoor
   , openDoor
   , getAdminAccess
   ) where

 getYourUser :: String -> String -> IO (User Noob)
 getYourUser username password = do
    db   <- openDB
    user <- queryDB db username password
    closeDB db
    return user

 createNewUser :: User Admin -> String -> (Int -> IO Int) -> IO ()
 createNewUser _ username opendoors
   = openDB >>= createUser username opendoors >>= closeDB

 openSecretDoor :: User Admin -> IO (Maybe Int)
 openSecretDoor _ = pure $ Just 1234

 openDoor :: User a -> Int -> IO Int
 openDoor = _openDoor

 getAdminAccess :: User a -> IO (Maybe (User Admin))
 getAdminAccess (User username opener) = do
   db    <- openDB
   isAdm <- verifyPermission username
   let user = if isAdm
		then Just $ User username opener
		else Nothing

As funções se tornaram mais simples pois não existe necessidade de verificar se o usuário é Admin para operações exclusivas, a própria função não aceita outro tipo de usuário.

Note que na função getAdminAccess, a instrução Just $ User username opener faz uma cópia do usuário original, porém mudando o tipo para User Admin.

3.2 Tipos fantasmas numa linguagem não funcional

Para garantir algumas propriedades em diversos tipos de árvores como Roseiras (Rose Trees) ou Árvores Rubro-Negras, podemos usar tipos fantasmas. Dê uma olhada neste link caso tenha curiosidade.

Tipos fantasmas, contudo, não são exclusividade de linguagens como Haskell. Também somos capazes de expressá-los em Java por exemplo.

Vamos tomar como exemplo uma aplicação onde só possamos enviar para o nosso banco de dados strings que foram higienizadas (sanitized), sob pena de sofrermos algum ataque de SQL Injection, por exemplo.

Podemos tentar uma primeira solução assim:

public static void runOnDB(String sql) {
    //...
}
public static String sanitize(String sql) {
    // Do work
    return sql;
}
public static void main(String args[]) {
    String sql = "blah blah; drop database;";
    runOnDB(sanitize(sql)); //Compiler is ok with this
    runOnDB(sql); //But also with this
}

Neste exemplo temos uma função runOnDB que executa um SQL no banco, uma função sanitize que limpa a string e finalmente uma função main que executa alguns statements no banco.

Note que neste exemplo, o desenvolvedor é obrigado a lembrar por conta própria (isto é, o compilador não o auxilia de maneira nenhuma) que é preciso higienizar a string antes de enviá-la ao banco. Na primeira chamada (dentro da função main) o desenvolvedor lembrou, mas na segunda chamada o sql passado como parâmetro não foi higienizado e vai tocar o horror no banco de dados.

Dá para melhorarmos um pouco:

class SanitizedString {
    private String contents;
    private SanitizedString(String str) {
	contents = str;
    }
    public static SanitizedString sanitize (String str) {
	//do stuff
	return SanitizedString(str);
    }
}

public static void runOnDB(SanitizedString sql) {...}

public static void main(String args[]) {
    String sql = "blah blah; drop database;";
    runOnDB(sanitize(sql)); //Compiler is ok with this
    runOnDB(sql); //But does not like this! Nice!
}

Agora sim, é impossível passar uma string não higienizada para o BD. O tipo da função runOnDB exige um SanitizedString como parâmetro e a única maneira de criar um valor deste tipo é através do método sanitize. O exemplo igual ao acima passa a causar um erro de compilação! O compilador passa a ajudar o desenvolvedor.

Contudo essa abordagem não é de todo sem limitações. Suponha que agora queiramos duas verificações na string a ser enviada para o BD. Vamos dizer que a string deveria ser validada e higienizada. Podemos querer uma ou ambas verificações. Seguindo a mesma ideia o nosso código ficaria:

class SanitizedString {...}
class ValidatedString {...}

class SanitizedAndValidated {...}

// Sanitized AND Validated
public static void runOnDB(SanitizedAndValidated str) {...}
//Sanitized only
public static void runSanitized(SanitizedString str) {...}
//Validated only
public static void runValidated(ValidatedString str) {...}

Não tão belo, mas ainda tratável. E se quisermos três validações: higienizada, validada e normalizada (maiúsculas/minísculas)?

class SanitizedString {...}
class ValidatedString {...}
class CapitalizedString {...}

class SanitizedAndValidated {...}
class SanitizedAndCapitalized {...}
class ValidatedAndCapitalized {...}
class SanitizedValidatedAndCapitalized {...}

E se agora quisermos saber se a string foi convertida para UTF-8?

class SanitizedString {...}
class ValidatedString {...}
class CapitalizedString {...}
class UTF8Converted {...}

...
...

Logo dá para ver que essa abordagem não escala bem. Precisamos de 7 combinações para 3 validações, 15 combinações para 4 validações, …

Dá pra fazer melhor? Conseguimos usar em Java a mesma ideia de tipos fantasmas que mostramos há pouco em Haskell?

Vamos começar com uma validação:

public class CheckedString1<T> {
    private String contents;
    private CheckedString1(String str) {
	contents = str;
    }
    public String getContents() {
       return contents;
    }
}

public class Sanitized {
   private Sanitized() {}
   public static CheckedString1<Sanitized> sanitize (String str) {
       //sanitizes and creates a CheckedString
       return new CheckedString1<Sanitized>(str);
   }
}

public class Validated {
   private Validated() {}
   public static CheckedString1<Validated> validate (String str) {
       //validates string, returns CheckedString
       return new CheckedString1<Validated>(str);
   }
}

Note que assim como tínhamos feito em Haskell, agora a nossa classe CheckedString1 tem um parâmetro de tipo T, que não é utilizado diretamente na implementação, mas serve para o compilador nos ajudar a verificar se tudo está conforme esperávamos.

Agora basta criamos os métodos que lidam com a validação que queremos e deixar que o compilador faça o trabalho duro de garantir que tudo está dentro do esperado:

public void runSanitized(CheckedString1<Sanitized> str) {...}
public void runValidated(CheckedString1<Validated> str) {...}

Mas e se quisermos duas validações? Também dá!

public class CheckedString2<T1, T2> {
    private String contents;
    public CheckedString2(String str,
			   Function<String, CheckedString1<T1>> f1,
			   Function<String, CheckedString1<T2>> f2) {
	String c1 = f1.apply(str).getContents();
	String c2 = f2.apply(c1).getContents();
	contents = c2;
    }
}

// Sanitized AND Validated
public void runOnDB(CheckedString2<Sanitized, Validated> str){...}

E podemos usar assim:

CheckedString2<Sanitized, Validated> sAndV =
  new CheckedString2<Sanitized, Validated>(
    sql,
    Sanitized::sanitize,
    Validated::validate);

runOnDB(sAndV);

Mas e se quisermos três?

public class CheckedString3<T1, T2, T3> {
...

Já tá começando a ficar chato… Note que apesar de termos melhorado o problema que tínhamos antes (precisávamos de 7 combinações para 3 checagens, 15 para 4, … e agora precisamos de apenas 1 nova classe CheckedStringN para fazer n checagens) ainda é necessário criar uma nova classe para cada número de validações desejado e a ordem das validações deve ser sempre a mesma!

Mas não era bem isso que queríamos. O que queremos, na verdade, é usar uma lista de checagens de tamanho arbitrário como o tipo fantasma da nossa String! Em outras palavras, queremos uma lista funcione no nível dos tipos!

Dá pra fazer isso em Java? Infelizmente não2. Mas é claro que conseguimos fazer isso em Haskell! \o/ Nós voltaremos a este exemplo quando falarmos de Type Families.

4 Disclaimer

Estes slides foram preparados para os cursos de Paradigmas de Programação e Desenvolvimento Orientado a Tipos na UFABC.

Este material pode ser usado livremente desde que sejam mantidos, além deste aviso, os créditos aos autores e instituições.

  1. Essa definição é correta e poderia ser aceita pelo compilador, mas não é o caso. A sintaxe tem um tratamento especial para [] já que colchetes e listas são uma parte tão importante da linguagem. Ainda é possível definir listas idênticas à padrão usando apenas nomes diferentes, por exemplo: data Lista a = Vazia | Nó a (Lista a) ↩︎

  2. Você não achou que nós falaríamos de Java neste site gratuitamente e se não fosse para malhar Java um pouquinho, achou? 😝 ↩︎