Tipos e Polimorfismo

1 Tipos, quem são, onde vivem e o quê comem

No post anterior nós descrevemos como tipos podem ser usados para restringir o conjunto de programas válidos. Esta restrição é feita de forma que o compilador possa nos avisar sobre alguns tipos de erros e assim para que possamos ter algumas garantias sobre o comportamento do programa quando ele for executado.

Em um dos exemplos, tentamos calcular a raiz quadrada de algo que não fosse um número. Em Python, isso tem a seguinte cara:

# Python
import math

str = "Hello World!"
print(math.sqrt(str))

Neste caso, quando a função sqrt for chamada o tipo do parâmetro que é uma string será verificado e um erro durante a execução ocorrerá.

A linguagem Python tem como uma de suas características a tipagem dinâmica. Isso significa que os tipos dos valores e a compatibilidade destes tipos com as operações são checadas apenas durante a execução do programa. Isso faz com que diversos testes, que poderiam ser feitos durante a compilação, sejam feitos apenas durante a execução.

Linguagens com tipagem estática, como Haskell, exigem que os tipos de todos os valores sejam conhecidos durante a compilação. Com esse conhecimento, o compilador pode então evitar erros como o que está presente no código em Python acima. De fato se tentarmos fazer isto:

main =
  let str = "Hello World!" in
  print $ sqrt str

Vamos receber um erro parecido com este aqui:

• No instance for (Floating [Char]) arising from a use of ‘sqrt’

Que indica que [Char], ou lista de caracteres ou simplesmente String não é um tipo que pertença a classe Floating. Vamos falar logo mais sobre typeclasses e destrinchar esse erro com mais atenção.

Existe uma longa discussão sobre o que é melhor, uma linguagem com tipagem dinâmica ou uma linguagem com tipagem estática. Existem argumentos bem convincentes para cada uma das abordagens e não discutiremos este tópico nestes posts. Aliás, dado o título desta série de posts vocês já devem desconfiar qual é a abordagem que nós achamos mais interessante dentre as duas né? 😝

1.1 Mas enfim, o que são tipos?

Podemos pensar em um tipo como um conjunto de valores. Vamos tomar como exemplo alguns tipos básicos em Haskell:

• Bool - Representa valores booleanos. É um tipo que contém apenas dois valores: True e False.
• Int - Representa inteiros. Em particular, a especificação garante que ele será um inteiro entre pelo menos \(-2^{29}\) até \(2^{29}-1\).
• Float - Representa números fracionários com precisão simples.

Estes tipos podem ser vistos como conjuntos com um número finito de elementos, ou seja, tanto para Bool, quanto para Int e Float o número de valores destes tipos é limitado.

Existem alguns outros tipos que, ao contrário destes que acabamos de apresentar, têm um número infinito de valores possíveis.

• Integer - Números inteiros de precisão arbitrária
• String - Todos os textos possíveis, de todos os comprimentos.

Em Haskell nós podemos indicar o tipo de funções com uma assinatura de tipo (type signature). Por exemplo:

soma :: Int -> Int -> Int -- Assinatura de tipo
soma a b = a + b          -- Corpo da função

A função soma recebe dois parâmetros inteiros, representados pelo tipo Int e devolve um outro inteiro. Note que ao incluir a assinatura de tipos na função nós estamos restringindo quais valores são aceitáveis como entradas e saída para a função. Qualquer tentativa de chamar a função com um valor que não seja um inteiro vai causar um erro de compilação.

Para inspecionar o tipo de um valor, podemos usar o comando :type ou simplesmente :t do GHCI.

Prelude> :type "UFABC"
"UFABC" :: [Char]
Prelude> :t "a"
"a" :: [Char]
Prelude> :t 'a'
'a' :: Char
Prelude>  let x = "Variável"
Prelude> :t x
x :: [Char]

Podemos também verificar o tipo da nossa função soma:

:t soma

Saída:

>>>
soma :: Int -> Int -> Int

Em alguns momentos é interessante termos o poder de especificar exatamente qual é o tipo de uma expressão. Por exemplo, o tipo de 3 + 4 pode ser Int, Integer, Float, Double, …

Assim como podemos usar :: para indicar o tipo de uma função (o tipo de uma função é dado pelas entradas e pela saída), também podemos fazer o mesmo usando uma anotação de tipo (type annotation) para uma expressão ou variável.

Prelude> x = (3 + 4) :: Int
Prelude> y = (3 + 4) :: Float
Prelude> :t x
x :: Int
Prelude> :t y
y :: Float

Note que se tirarmos a nossa anotação de tipo, a expressão de x e de y é idêntica!

Se tentarmos usar a nossa função soma com x, tudo ocorre conforme esperaríamos:

Prelude> soma x x
14

Mas reparem o que ocorre quando quando tentamos usar a nossa função soma definida acima quando tentamos somar y que é um Float:

Prelude> soma y y

<interactive>:36:6: error:
    • Couldn't match expected type ‘Int’ with actual type ‘Float’
    • In the first argument of ‘soma’, namely ‘y’
      In the expression: soma y y
      In an equation for ‘it’: it = soma y y

<interactive>:36:8: error:
    • Couldn't match expected type ‘Int’ with actual type ‘Float’
    • In the second argument of ‘soma’, namely ‘y’
      In the expression: soma y y
      In an equation for ‘it’: it = soma y y

Como era de se esperar! Dissemos que o tipo de soma :: Int -> Int -> Int só aceita inteiros e tentamos passar um valor do tipo errado.

Como fazer, então, soma funcionar tanto para Int quanto para Float?

Se tirarmos a assinatura da função soma, tudo parece funcionar corretamente:

Prelude> soma2 a b = a + b
Prelude> soma2 x x
14
Prelude> soma2 y y
14.0

Vamos olhar o tipo inferido de soma2:

Prelude> :t soma2
soma2 :: Num a => a -> a -> a

O que é esse Num? O que é esse a?

1.2 Typeclasses

(Uma apresentação mais pormenorizada de typeclasses pode ser vista aqui)

Na seção anterior terminamos com o exemplo de uma soma. Se não declararmos o tipo da função soma2 explicitamente, o compilador infere que o tipo é soma2 :: Num a => a -> a -> a. Vamos agora destrinchar esta assinatura.

A parte à esquerda do => contém restrições de classe (class constraints). A restrição Num a declara a, uma variável de tipo (type variable), e restringe que essa variável só pode ser de tipos que pertençam à typeclass Num.

Uma typeclass pode ser encarada como um conjunto de tipos que que encerram alguma relação em comum. Por exemplo, todos os tipos que podem ser comparados por igualdade pertencem à classe Eq. Os tipos que têm um limite superior e inferior de valores pertencem à classe Bounded. Frequentemente classes de tipo também estabelecem algumas operações ( métodos - methods) válidas para cada um dos valores dos tipos que a pertencem. Por exemplo, Eq define o método == e Bounded define os métodos minBound e maxBound.

Num é a typeclass que abriga valores de tipos numéricos. Se usarmos o GHCI e o comando :info, ou simplesmente :i podemos obter mais informações sobre qualquer typeclass:

Prelude> :info Num
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
  {-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-}
	-- Defined in ‘GHC.Num’
instance Num Word -- Defined in ‘GHC.Num’
instance Num Integer -- Defined in ‘GHC.Num’
instance Num Int -- Defined in ‘GHC.Num’
instance Num Float -- Defined in ‘GHC.Float’
instance Num Double -- Defined in ‘GHC.Float’

Vamos deixar a primeira linha (type Num :: * -> Constraint) de lado por um instante. Voltaremos a falar dela em mais detalhes em posts mais adiante.

As linhas seguintes mostram a definição da classe Num que tem os métodos (+), (-), (*), … Enfim, operações comuns a diversos tipos númericos. Em seguida são listados os métodos obrigatórios para aqueles que desejem criar uma nova instância (instance) da classe (ou seja, que queiram dizer que um tipo pertence àquela classe) e as instâncias conhecidas.

É por isso que quando pedimos para o GHC inferir o tipo de soma2 ele inferiu soma2 :: Num a => a -> a -> a. A única coisa que ele sabia sobre os parâmetros a e b é que eles poderiam ser somados com (+), e o tipo deste metódo é válido apenas para a em Num.

Legal, já sabemos ler a assinatura. Também sabemos que x é um Int, y é um Float e também sabemos que Int e Float têm instâncias de Num. Então é razoável supor que podemos calcular x + y, ou de maneira equivalente, soma2 x y já que as suas asinaturas são as mesmas:

Prelude> :t (+)
(+) :: Num a => a -> a -> a
Prelude> :t soma2
soma2 :: Num a => a -> a -> a

Esse fato (que soma2 é igual a (+)) fica mais evidente se usarmos uma implementação no estilo sem pontos (point-free style):

soma2 = (+)

Contudo se tentarmos somar x e y recebemos um erro:

Prelude> x + y

<interactive>:51:5: error:
    • Couldn't match expected type ‘Int’ with actual type ‘Float’
    • In the second argument of ‘(+)’, namely ‘y’
      In the expression: x + y
      In an equation for ‘it’: it = x + y

Note que a assinatura de (+) especifica que a pode ser qualquer tipo que pertença a classe Num. Mas também especifica que ambos os tipos dos parâmetros de (+) devem ser a, ou seja, os mesmos (assim como o valor de retorno).

Haskell, ao contrário de outras linguagens de programação, não faz conversões implícitas de valores de quaisquer tipos (JavaScript e PHP estou olhando para vocês!). Então, se desejamos somar um número inteiro e um fracionário (ou qualquer outro número cuja classe esteja em Num), precisamos deixar isso claro na assinatura da função e fazer as devidas conversões explicitamente.

Uma primeira tentativa poderia ser feita com algo na seguinte linha:

soma3 :: (Num a, Num b, Num c) => a -> b -> c
soma3 a b = a + b

Mas essa implementação também não é válida. Apesar dos parâmetros serem dos tipos corretos, (+) ainda aguarda parâmetros do mesmo tipo. Poderíamos tentar converter b para o tipo de de a (ou vice versa). Mas também não conseguimos! Veja a lista dos métodos de Num. Dentre eles não há nenhum que possamos usar para converter b, não sabemos de verdade quem é b, apenas que ele é um tipo pertencente a Num. Vamos ver num post mais adiante, quando falarmos de type families, uma possível solução para conseguirmos implementar tal função.

2 Polimorfismo

Polimorfismo em Haskell vem, basicamente, em dois sabores:

• Polimorfismo paramétrico (parametric polymorphism): ocorre quando temos variáveis de tipos na assinatura de uma função ou de um tipo de dados. Neste caso, a mesma função pode trabalhar com parâmetros de diversos tipos contanto que os seus tipos “encaixem”¹ com os tipos concretos que estamos trabalhando.

• Polimorfismo ad-hoc (ad-hoc polymorphism): ocorre quando utilizamos typeclasses e temos diversos tipos que são instâncias de uma mesma typeclass. Nesses casos o sistema de execução do haskell escolhe a implementação apropriada de uma função baseada no tipo específico do valor em questão.

  A principal diferença entre polimorfismo paramétrico e polimorfismo ad-hoc é que no primeiro caso as funções usam uma única implementação para trabalhar com diversos tipos diferentes. Já no segundo caso, o polimorfismo ad-hoc, podem haver diversas implementações diferentes da mesma função e uma delas é escolhida em função dos tipos envolvidos.

  Vamos dar uma olhada em alguns exemplos de cada tipo de polimorfismo.

2.1 Polimorfismo paramétrico

Vamos considerar o exemplo da função len que calcula o comprimento de uma lista. Aqui está o seu código completo:

len :: [a] -> Int
len [] = 0
len (_:xs) = 1 + len xs

A assinatura da função length contém uma variável de tipos (a) mas como não precisamos saber nada a respeito de a, não lhe é colocada nenhuma restrição.

Podemos aplicar a função len a uma lista de Int, String, Char, … e a função continua a fazer o seu trabalho:

Prelude> len [1,2,3]
3
Prelude> len ["Olá", "Mundo", "!"]
3
Prelude> len "UFABC"
5

Este tipo de polimorfismo é tão natural que por vezes nem nos damos conta de que ele de fato está ali.

Existem também funções polimórficas que modificam o seu tipo de retorno baseando-se em um dos seus parâmetros ou até no contexto onde ela foi chamada. Vejamos alguns exemplos:

-- O tipo de retorno depende do tipo de entrada
first :: [a] -> a
first (x:_) = x
first _     = error "A lista precisa ter ao menos um elemento"

-- O tipo de retorno depende do contexto da chamada
segredo :: Num a => a
segredo = 42

No primeiro caso, o tipo de retorno depende de um dos tipos de entrada. Assim, quando for feita a chamada da função com um valor (que tem um tipo) o tipo do valor do retorno é automaticamente determinado. Veja um exemplo de chamada:

-- Como xs tem tipo [Int], automaticamente é como se first passasse a
-- ter no contexto dessa chamada o tipo first :: [Int] -> Int. O mesmo
-- ocorre para ys, onde o tipo de first é como se fosse
-- first :: [Char] -> Char
foo :: [Int] -> [Char] -> (Int, Char)
foo xs ys = (first xs, first ys)

Já no segundo caso, o tipo de retorno é definido pelo contexto onde é feita a chamada. Considere os seguintes exemplos:

-- Aqui segredo precisa ser do tipo Int para (+) poder ser aplicado,
-- já que x é Int.
foo :: Int -> Int
foo x = x + segredo

-- Neste caso, segredo precisa ser Float para poder encaixar com o
-- tipo de bar
bar :: Float
bar = segredo

-- Finalmente, segredo precisa se tornar compatível com a chamada de
-- (*), como x é Double o retorno de segredo também precisa ser
baz :: Double -> Double
baz x = x * segredo

Em ambos os casos, first e segredo existe um quantificador universal (\(\forall\)) implícito para cada uma das variável de tipos. Nós podemos tornar este quantificador explícito reescrevendo as funções da seguinte maneira:

{-# LANGUAGE ExplicitForAll #-}

first :: forall a. [a] -> a
first (x:_) = x
first _     = error "A lista precisa ter ao menos um elemento"

segredo :: forall a. Num a => a
segredo = 42

Agora que já entendemos o funcionamento de funções polimórficas, podemos começar a explorar uma versão mais avançada do conceito que é o uso de funções que recebem argumentos polimórficos .

Vamos ver um exemplo de como isso pode funcionar. Considere o seguinte trecho de código:

aplicaEDevolvePar :: (Num a, Num b, Num c) => (a -> a) -> b -> c -> (b, c)
aplicaEDevolvePar f b c = ...

A função aplicaEDevolvePar recebe uma função f de tipo (a -> a), dois parâmetros de tipos b e c; e devolve uma tupla (b, c).

Se tentarmos fazer:

aplicaEDevolvePar :: (Num a, Num b, Num c) => (a -> a) -> b -> c -> (b, c)
aplicaEDevolvePar f x y = (f x, f y)

É razoável esperar que tal chamada fosse legal:

bar :: (Int, Float)
bar = aplicaEDevolvePar (^2) 42 3.1415

Os tipos todos parecem bater. (^2) :: Num a => a -> a é como esperado, e f x portanto tem tipo igual a x, f y igual a y… Contudo, se tentarmos compilar esse código, recebemos o seguinte erro:

src/Main.hs:105:30: error:
    • Couldn't match expected type ‘a’ with actual type ‘b’
      ‘b’ is a rigid type variable bound by
	the type signature for:
	  aplicaEDevolvePar :: forall a b c.
			       (Num a, Num b, Num c) =>
			       (a -> a) -> b -> c -> (b, c)
	at src/Main.hs:104:1-74
      ‘a’ is a rigid type variable bound by
	the type signature for:
	  aplicaEDevolvePar :: forall a b c.
			       (Num a, Num b, Num c) =>
			       (a -> a) -> b -> c -> (b, c)
	at src/Main.hs:104:1-74
    • In the first argument of ‘f’, namely ‘x’
      In the expression: f x
      In the expression: (f x, f y)
    • Relevant bindings include
	x :: b (bound at src/Main.hs:105:21)
	f :: a -> a (bound at src/Main.hs:105:19)
	aplicaEDevolvePar :: (a -> a) -> b -> c -> (b, c)
	  (bound at src/Main.hs:105:1)
    |
105 | aplicaEDevolvePar f x y = (f x, f y)
    |                              ^

O erro se repete para o f y. O que está acontecendo aqui?

O problema aqui está no quantificador universal implícito criado pelo compilador. Vamos escrevê-lo explicitamente para deixar o problema mais evidente. Note que o erro acima já fez isso para nós!

aplicaEDevolvePar :: forall a b c.
		     (Num a, Num b, Num c) =>
		     (a -> a) -> b -> c -> (b, c)
aplicaEDevolvePar f x y = (f x, f y)

Assim como tínhamos dito anteriormente, essa chamada vai fixar os tipos concretos de a, b e c. Uma vez fixados, os tipos não mudam (sic). 😛 O que significa que o tipo representado por a é definido como sendo igual ao tipo de f x e que deve ser do mesmo tipo de f y (já que o retorno de f é sempre a). Isso implica que os tipos de x e y devem ser os mesmos, ou seja, que b é igual a c. Isso é, contudo, um absurdo já que o quantificador universal no início da função afirma que os tipos valem para todos a, b e c, sejam eles quais forem!

Jogamos a toalha? Não tem solução?

Claro que tem! Nós podemos indicar que a função f é polimórfica, e forçar que a decisão dos tipos de f seja tomada diretamente nos locais onde ela é chamada! Fica assim:

{-# LANGUAGE RankNTypes #-}

aplicaEDevolvePar :: forall b c.
		     (Num b, Num c) =>
		     (forall a. Num a => a -> a) -> b -> c -> (b, c)
aplicaEDevolvePar f x y = (f x, f y)

bar :: (Int, Float)
bar = aplicaEDevolvePar (^2) 42 3.1415

Agora, a função f se mantém polimórfica. Note a semelhança com o exemplo da função foo que chama a função first, que descrevemos acima e que repetimos aqui para facilitar a vida do caro leitor:

first :: forall a. [a] -> a
first (x:_) = x
first _     = error "A lista precisa ter ao menos um elemento"

foo :: [Int] -> [Char] -> (Int, Char)
foo xs ys = (first xs, first ys)

Outro exemplo, imagine que queiramos escrever uma função que recebe dois valores da classe Show, converte-os para string usando uma função recebida como parâmetro, e devolve as strings desses valores concatenadas e separados por “-”. Uma possível implementação poderia ter essa cara:

concatena :: (Show a, Show b, Show c) => (a -> String) -> b -> c -> String
concatena toString str1 str2 = toString str1 ++ "-" ++ toString str2

main :: IO ()
main = putStrLn $ concatena (\x -> "<" ++ show x ++ ">") "senha" 12345

Apesar de parecer razoável, essa implementação não funciona. Ela sofre do mesmo problema da anterior. Como consertar?

concatena :: (Show b, Show c) =>
	     (forall a. Show a => a -> String) -> b -> c -> String
concatena toString str1 str2 = toString str1 ++ "-" ++ toString str2

main :: IO ()
main = putStrLn $ concatena (\x -> "<" ++ show x ++ ">") "senha" 12345

2.2 Polimorfismo ad-hoc

Apesar de termos dito acima, em uma linda caixinha de warning, que classes e instâncias em Haskell não tem relação alguma com suas colegas homônimas de programação orientada a objetos (POO), é inevitável que notemos algumas semelhanças.

Typeclasses permitem que façamos em Haskell um tipo de polimorfismo que se assemelha muito àquela tão conhecida ligação dinâmica (dinamic dispatch) presente nas linguagens de programação orientadas à objeto (OO).

Vamos começar com um exemplo simples que devolve o nome do tipo de um valor.

class Tipavel a where
  nomeTipo :: a -> String

Agora, podemos implementar as instâncias que desejamos para esta classe:

instance Tipavel Int where
  nomeTipo _ = "Int"
instance Tipavel Float where
  nomeTipo _ = "Float"
instance Tipavel Double where
  nomeTipo _ = "Double"
instance Tipavel Char where
  nomeTipo _ = "Char"

Isso funciona exatamente como esperávamos! Note que é preciso indicar, com uma anotação de tipos, se 3 é um Int ou um Float, caso contrário o GHC não é capaz de decidir qual dos “3s” disponíveis queremos (Int, Integer, Float, Double, Word, …).

*Main> nomeTipo (3 :: Int)
"Int"
*Main> nomeTipo 'A'
"Char"
*Main> nomeTipo (3 :: Float)
"Float"

Aqui temos, então, um exemplo de polimorfismo ad-hoc. A depender do tipo do parâmetro passado para a função nomeTipo uma implementação diferente é escolhida.

Em linguagens de programação orientadas a objeto, uma série de regras (nem sempre tão simples) são usadas para escolher a implementação. Por exemplo, se a linguagem tiver herança múltipla/hierarquia + interfaces/… e houver conflito de nomes, qual implementação deve ser escolhida? Python usa um mecanismo chamado linearização C3; Lisp permite que o esquema seja completamente configurado em tempo de execução (há inclusive um livro sobre este assunto); R decide usando ordem alfabética; Java exige que o desenvovedor indique explicitamente qual implementação deve ser escolhida, …

Em linguagens orientadas a objeto é comum fazer isso carregando um dicionário de métodos juntamente com o objeto. Essa é a abordagem usada por Python e Smalltalk nos quais você pode, inclusive, bagunçar com o dicionário para fazer as mais diversas peripécias. Em C++, por exemplo, pode-se declarar métodos como virtual o que indica ao compilador que ele deve fazer a ligação dinamicamente (o padrão é fazer isso estaticamente). Para isto C++ usa uma vtable (Virtual Method Table) que nada mais que uma releitura dos dicionários de Smalltalk e Python em C++.

Haskell tem um sistema de tipos forte e não é orientado a objetos. Essas características fazem com que seja desnecessário ter uma estrutura semelhante à vtable do C++ ja que, se em algum ponto do código houver uma variável de tipo que não puder ser resolvida, o compilador grita com um erro.

Considere a seguinte função que trabalha com a nossa classe de tipos Tipavel:

tipoInteiro :: Tipavel a => a -> Bool
tipoInteiro x = nomeTipo x `elem`  ["Int", "Integer"]

A função tipoInteiro é polimorfica em seu argumento (a) que é restrito apenas aos tipos que tem uma instância para Tipavel. E é justamente aqui que está o pulo do gato: durante a compilação, o GHC transforma a => em -> ! Em outras palavras, uma restrição de tipos se torna um novo parâmetro da função. Isso traz algumas consequências interessantes.

A primeira delas é que isso significa que você pode usar => várias vezes na sua assinatura. Por exemplo: Ord a => Ord b => a -> b -> Bool é exatamente a mesma coisa que (Ord a, Ord b) => a -> b -> Bool. O GHCI inclusive converte de um formato para o outro para você:

foo :: (Ord a, Ord b, Ord c, Ord d) => (a, b, c, d) -> (d, c, b, a)
foo = undefined

bar :: Ord a => Ord b => Ord c => Ord d => (a, b, c, d) -> (d, c, b, a)
bar = undefined

Prelude> :t foo
foo :: (Ord a, Ord b, Ord c, Ord d) => (a, b, c, d) -> (d, c, b, a)
Prelude> :t bar
bar :: (Ord a, Ord b, Ord c, Ord d) => (a, b, c, d) -> (d, c, b, a)

A segunda é que apesar da função tipoInteiro receber apenas um argumento, do ponto de vista do sistema de execução ela recebe 2: um dicionário (que contém os métodos da instância da classe para o tipo restringido) e o parâmetro propriamente dito. Este mecanismo de passagem de dicionários na calada da noite para implementar polimorfismo é chamado de dictionary-passing style [4].

A implementação do GHC para polimorfismo ad-hoc é um pouco mais complicada do que a simplificação usando dicionários que descrevemos aqui. A primeira metade da palestra do Simon Peyton Jones [6] explica em mais detalhes como que isso é realmente implementado.

Contudo se nos restringirmos ao padrão Haskell sem as extensões do GHC, podemos continuar a pensar que, como em Haskell os tipos podem ser determinados em tempo de compilação (pois caso contrário o compilador berra com um belo erro Ambiguous type variable), um dicionário² onde as chaves são os nomes dos métodos e os valores são as funções, é o suficiente para encontrarmos a implementação desejada. Mais detalhes podem ser vistos no trabalho de Peterson e Jones [5].

Se repararmos no uso que fizemos da classe Tipavel veremos que o valor do parâmetro para a função nomeTipo nunca é usado. Na verdade, o parâmetro só está lá para que o GHC tenha uma maneira de escolher a implementação desejada baseada no seu tipo.

Isso significa que nem precisaríamos, a priori, de um valor válido para chamar a implementação. Considere o código abaixo:

*Main> nomeTipo (undefined :: Int)
"Int"
*Main> nomeTipo (undefined :: Float)
"Float"

Será que precisamos realmente deste valor postiço?

Vamos alterar a nossa typeclass para adicionar um novo método que não recebe parâmetro algum (juntamente com as implementações correspondentes):

class Tipavel a where
  nomeTipo :: a -> String
  nomeTipo _ = nomeTipo0

  nomeTipo0 :: String

instance Tipavel Int where
  nomeTipo0 = "Int"
instance Tipavel Float where
  nomeTipo0 = "Float"
instance Tipavel Double where
  nomeTipo0 = "Double"
instance Tipavel Char where
  nomeTipo0 = "Char"

Esse código quase funciona®. Ele vai reclamar que não é capaz de determinar qual método nomeTipo0 (sendo mais preciso, a implementação de qual instância para nomeTipo0) deve ser usada na implementação padrão de nomeTipo. Antes a determinação era feita pelo tipo do parâmetro. Isso, como vimos na seção anterior, causava a passagem implícita do dicionário para a escolha do método. Mas como agora não tem parâmetro nenhum, tampouco há dicionário associado.

Para contornar este problema nós podemos aplicar um tipo (ou seja, passar um dicionário específico por baixo dos panos). Isso é feito usando um @ seguido do tipo. Vejamos no exemplo:

{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE ScopedTypeVariables #-}

class Tipavel a where
  nomeTipo :: a -> String
  nomeTipo _ = nomeTipo0 @a

  nomeTipo0 :: String

instance Tipavel Int where
  nomeTipo0 = "Int"
instance Tipavel Float where
  nomeTipo0 = "Float"
instance Tipavel Double where
  nomeTipo0 = "Double"
instance Tipavel Char where
  nomeTipo0 = "Char"

Agora podemos usar a função nomeTipo exatamente como usávamos antes, mas também podemos usar nomeTipo0:

*Main> nomeTipo (undefined :: Float)
"Float"
*Main> nomeTipo0 @Float
"Float"
*Main> nomeTipo0 @Int
"Int"

Entendido o funcionamento, vamos fazer agora um exemplo mais interessante, um código para conversão de unidades de peso. Vamos começar definindo tipos para cada uma das unidades que desejamos.

data Grama
data Kilograma
data Onça
data Libra
data Pedra

A palavra reservada data cria um novo tipo de dados. Aqui estamos criando apenas um tipo, sem nenhum construtor. Ou seja, é um tipo não habitado . Para mais informações sobre criação de tipos veja aqui e também aqui.

Agora que temos nossos os tipos que representam as unidades, nada mais justo que também criarmos uma typeclass para o conjunto dos tipos que representam unidades e suas respectivas instâncias.

class Unidade u where
  sigla :: String
  fator :: Floating a => a

instance Unidade Grama where
  sigla = "g"
  fator = 1

instance Unidade Kilograma where
  sigla = "kg"
  fator = 1000

instance Unidade Onça where
  sigla = "oz"
  fator = 28.35

instance Unidade Libra where
  sigla = "lb"
  fator = 453.59

instance Unidade Pedra where
  sigla = "st"
  fator = 14 * fator @Libra

Nossa typeclass tem dois métodos. sigla devolve a sigla daquela unidade e fator que devolve o fator de conversão da unidade para o padrão do SI (grama). Note que na unidade pedra usamos a definição de libras, com uma aplicação de tipos.

Agora é preciso que definamos uma função de conversão. Como queremos que essa função seja polimórfica no tipo (na unidade), e como nossos tipos não são habitados, vamos usar polimorfismo ad-hoc com type applications. Para isto, vamos criar uma typeclass que representa a conversão de unidades com uma única instância:

class Conv a b where
  conv :: Floating f => f -> f

instance (Unidade a, Unidade b) => Conv a b where
  conv x = x * fator @a / fator @b

A função conv converte um valor na unidade representada pelo tipo a na unidade representada pelo tipo b. Para usar basta usar aplicações de tipo!

convOzLibra :: Floating f => f -> f
convOzLibra x = conv @Onça @Libra x

Prelude> convOzLibra 13
0.8125179126523954
Prelude> conv @Pedra @Grama 0.4
2540.104

Mas para que tudo isso?

Você que chegou até aqui pode estar se perguntando: “Pra quê? Veja só essa linda outra implementação alternativa que fiz que não usa nada dessas firulas!”

data Unidade = Grama | Kilograma | Onça | Libra | Pedra

fator :: Floating f => Unidade -> f
fator = \case
  Grama     -> 1
  Kilograma -> 1000
  Onça      -> 28.35
  Libra     -> 453.59
  Pedra     -> 14 * fator Libra

sigla :: Unidade -> String
sigla = \case
  Grama     -> "g"
  Kilograma -> "kg"
  Onça      -> "oz"
  Libra     -> "lb"
  Pedra     -> "st"


conv :: Floating f =>  Unidade -> Unidade -> f -> f
conv u0 u1 x = x * fator u0 / fator u1

convOzLibra :: Floating f => f -> f
convOzLibra = conv Onça Libra

Que pode ser usada da seguinte maneira:

Prelude> convOzLibra 13
0.8125179126523954
Prelude> conv Pedra Grama 0.4
2540.104

Comparando a versão com type applications (conv @Pedra @Grama 0.4) com a versão tradicional (conv Pedra Grama 0.4) não parece termos ganhado grande coisa. Na verdade, até tivemos que digitar dois caracteres a mais na chamada, isso sem falar na implementação mais longa!

Então, nada mais justo que fazermos coro para a pergunta: “mas para que tudo isso?”

A verdade é que há sim uma diferença sutil. Neste segundo caso, na implementação tradicional, toda vez que uma sigla for pedida ou uma conversão for ser efetuada é necessário varrer cada uma das possibilidades dentro do case para encontrar a entrada relevante. Utilizar casamento de padrão diretamente no parâmetro da função teria o mesmo efeito. Em outras palavras, a escolha da implementação está sendo feita durante a execução e será feita repetidamente para cada uma das chamadas que forem efetuadas.

Já a versão com type application define a implementação a ser usada durante a compilação do código. Quando forem efetuadas chamadas durante a execução da aplicação não há o que ser escolhido, a implementação já está decidida e pronta para ser executada.

tl;dr Versão tradicional tem custos durante a execução: para \(n\) conversões teremos \(n\) varreduras para a escolha da implementação. Versão com type applications, não tem custos durante a execução: apenas uma única varredura para a escolha da implementação que é feita durante a compilação, independentemente do número de conversões.

Há, contudo, um outro aspecto a se considerar. O uso de type applications pode ser muito legal para quando temos o conhecimento, já em tempo de compilação, das conversões que desejo efetuar. Considere, por exemplo, que iremos perguntar ao usuário 3 informações: unidade origem, unidade destino e valor a ser convertido.

Vamos supor que isso chegue para nós através de uma função com essa cara:

-- Recebe as siglas das unidades de origem e destino e um
-- valor. Devolve o valor convertido da unidade de origem para
-- destino.
converteUsuario :: Floating f => String -> String -> f -> Maybe f
converteUsuario orig dest val = _

A implementação tradicional usando ADTs é bem fácil!

-- Alteramos ligeiramente a definição de Unidade para adicionar o deriving Enum
data Unidade = Grama | Kilograma | Onça | Libra | Pedra deriving (Enum)

converteUsuario :: Floating f => String -> String -> f -> Maybe f
converteUsuario orig dest val =
  conv <$> buscaUnidade orig <*> buscaUnidade dest <*> pure val
  where
    unidades = enumFrom (toEnum 0) :: [Unidade]
    buscaUnidade x = find ((x ==) . sigla) unidades

E o uso:

Prelude> converteUsuario "oz" "lb" (42 :: Float)
Just 2.625058

Como fazer o mesmo usando a implementação com type applications? Bom, existe uma maneira bem fácil de resolver usando type families. Veremos type families mais adiante no curso. contudo, precisamos resolver o nosso problema com os recursos que temos agora!

A primeira coisa que precisamos é conseguir transformar a string fornecida pelo usuário em um tipo durante a execução do programa. Com o tipo podemos então fazer um type application e está tudo resolvido.

Podemos começar a tentar fazer algo assim:

converteUnidadeParaTipo :: String -> ???
converteUnidadeParaTipo = ???

O problema aqui é qual é o tipo de retorno da função? Cada unidade é um tipo separado, então a nossa única opção seria uma variável de tipos que restringe o retorno para tipos com instâncias de Unidade.

converteUnidadeParaTipo :: Unidade u => String -> u
converteUnidadeParaTipo = ???

Feito! Vamos rechear a função:

converteUnidadeParaTipo :: Unidade u => String -> u
converteUnidadeParaTipo "g"= Grama
converteUnidadeParaTipo "kg"= Kilograma
...

Opa! mas isso é ilegal! Lembrem-se, os nossos tipos de unidade não são habitados! Precisamos de um representante para nossos tipos, um valor (de outro tipo) que seja capaz de “armazenar” o tipo que estamos interessados. Apesar do Haskell já dispor do tipo que precisamos, vamos criá-lo nós mesmos!

data Proxy a = Proxy

Este tipo é diferente. Note que ele armazena a informação de tipo mas o valor é único. Neste sentido não é diferente do unit (()). Mas ao contrário do unit, Proxy é um tipo paramétrico!

Agora podemos tentar consertar nossa implementação:

converteUnidadeParaTipo :: Unidade u => String -> Proxy u
converteUnidadeParaTipo "g"= Proxy :: Proxy Grama
converteUnidadeParaTipo "kg"= Proxy :: Proxy Kilograma
...

Que maravilha! O compilador berra novamente! Do que ele está reclamando agora? Note que apesar do valor de retorno em cada um dos casos ser sempre Proxy, o tipo é diferente! Na primeira linha é do tipo Proxy Grama, na segunda Proxy Kilograma, …

Droga! Vamos ter que tirar do armário as ferramentas mais pesadas!

Comecemos do fim para o começo. Vamos supor que já temos dois Proxy dos tipos certos, vamos implementar uma função convProxy que tem a assinatura abaixo:

convProxy :: forall a b f. (Unidade a, Unidade b, Floating f) =>
	     Proxy a -> Proxy b -> f -> f
confProxy = _

Essa assinatura merece alguns comentários. A função convProxy recebe 3 parâmetros. Um proxy cujo tipo indica a unidade de origem; um proxy cujo tipo indica a unidade de destino; e um valor de um tipo da classe Floating. Ao final, ela devolve um valor convertido do mesmo tipo de entrada, da classe Floating.

Como podemos utilizá-la? Lembrem-se que já usamos antes conv @Onça @Libra, e aqui podemos fazer a mesma coisa! (Note que precisamos da extensão ScopedTypeVariables para poder fazer a aplicação usando a mesma variável de tipo da assinatura da função).

-- Recebe dois proxies (cujo valor ignoramos) indicando unidades de
-- origem e destino. Os tipos dos proxies são usados no type
-- application para escolher a implementação apropriada
convProxy :: forall a b f. (Unidade a, Unidade b, Floating f) => Proxy a -> Proxy b -> f -> f
confProxy _ _ = conv @a @b

Voltemos agora ao problema inicial. Como gerar um proxy a partir de uma string? O que precisamos é forçar que o tipo de retorno da função seja dependente de uma das entradas, ou seja, queremos polimorfismo paramétrico. Mas a dependência não é dada diretamente pelo tipo das entradas, mas pelo seu conteúdo! Para fazer isso vamos novamente lançar mão da extensão RankNTypes.

aplicaPara :: forall b. String -> (forall a. Unidade a => Maybe (Proxy a -> b)) -> Maybe b
aplicaPara u f =
  if | sigla @Grama     == u -> jfp @Grama
     | sigla @Kilograma == u -> jfp @Kilograma
     | sigla @Onça      == u -> jfp @Onça
     | sigla @Libra     == u -> jfp @Libra
     | sigla @Pedra     == u -> jfp @Pedra
     | otherwise             -> Nothing
    where
      jfp :: forall u. Unidade u => Maybe b
      jfp = f <*> pure (Proxy @u)

converteUsuario :: forall f. (Floating f) =>
	       String -> String -> f -> Maybe f
converteUsuario orig dest val =
  aplicaPara dest (aplicaPara orig (Just convProxy)) <*> pure val

A assinatura da função converteUsuario é a mesma da versão tradicional. Contudo o seu corpo é bem diferente. Vamos analisar cada passo. O coração desta função é dado pela utilização da função aplicaPara. Ela recebe a string u contendo a sigla da unidade, uma função f a ser aplicada no proxy contendo o tipo da classe Unidade e devolve o resultado dessa aplicação. Aqui está o pulo do gato! Como f é polimórfica, o seu tipo de retorno só será determinado no local da sua utilização! Como o local de uso e portanto o tipo de retorno de f dependem do valor da string, e como o tipo de retorno de aplicaPara (b) está amarrado com o tipo de retorno de f (pois é a mesma variável de tipos), o tipo de retorno de aplicaPara passou a depender do valor da String!

Lançamos mão de outro truque nessa implementação. Note que o tipo de retorno de f é simplesmente b. Isso faz com que possamos aplicar a função parcialmente na primeira chamada (aplicaPara orig (Just convProxy)), o que nos resulta em, talvez, uma nova função que pode ser aplicada novamente na segunda chamada aplicaPara dest .... O resultado novamente é talvez uma função que é talvez aplicada em um valor usando o manjado operador apply (<*>) da classe Applicative.

Repare também na função aplicaPara que usa um truque polimórfico para definir a função jfp cujo tipo depende do contexto do seu uso. Em particular, note que a variável de tipos u não é usada na assinatura (apenas declarada) e usada para criação do proxy.

3 Referências

• [1]. https://en.wikibooks.org/wiki/Haskell
• [2]. Haskell generics explained
• [3]. Fluent Polymorphism with Visible Type Applications, Creative Commons BY-NC-SA 4.0
• [4]. https://www.cs.tufts.edu/comp/150PLD/Notes/TypeClasses.pdf
• [5]. Implementing Type Classes
• [6]. Simon Peyton Jones: how GHC type inference engine actually works

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.