Tipos de Dados Algébricos

Playlists

1 Criando novos tipos

  • Imagine uma função que recebe como primeiro argumento uma tupla contendo um identificador, um nome de produto e seu preço, um segundo argumento com o percentual de aumento, e retorna a tupla atualizada: 
    atualiza_preco :: (Integer, String, Double) -> Double -> (Integer, String, Double)
atualiza_preco (id_prod, nome, preco) inflacao = (id_prod, nome, preco*(1 + inflacao))

  • Sem uma documentação, a assinatura dessa função não torna claro seu objetivo:

    atualiza_preco :: (Integer, String, Double) -> Double -> (Integer, String, Double)
atualiza_preco (id_prod, nome, preco) inflacao = (id_prod, nome, preco*(1 + inflacao))

  • Descreve um produto pelo código, nome e preço?

  • Para piorar, podemos ter uma outra tupla do mesmo tipo descrevendo outro contexto:

    troco :: (Integer, String, Double) -> (Integer, String, Double) -> Double
troco (id_prod, nome, preco) (id_cli, nome_cli, pago) = pago - preco

  • Agora o Double da tupla representa valor pago.

  • Se não temos uma documentação, como saber a que se refere cada um dos argumentos? 
    troco :: (Integer, String, Double) -> (Integer, String, Double) -> Double
  • Para criarmos uma diferenciação entre tipos idênticos com contexto diferente, criamos novos tipos compostos de tipos elementares: 
    troco :: Produto -> Cliente -> Double
  • Em Haskell, uma forma de criar um tipo é com a palavra-chave type: 
    type Produto = (Integer, String, Double)
type Cliente = (Integer, String, Double)

pago  (_, _, p) = p
preco           = pago

troco :: Produto -> Cliente -> Double
troco produto cliente = pago cliente - preco produto

  • Note que type cria apenas um apelido para um certo tipo, ou seja, o seguinte código vai compilar:

    leite = (10, "leite", 2.5)
lucas = (2391, "Lucas", 10)

troco lucas leite

    Saída:

    
-7.5
  • Um exemplo de tipo que vocês já utilizaram e que é um apelido é a String: 
    type String = [Char]

  • Podemos também criar tipos paramétricos, ou seja, com uma ou mais variáveis de tipo em aberto:

    type Assoc k v = [(k,v)]

find :: Eq k => k -> Assoc k v -> v
find k t = head [v | (k',v) <- t, k == k']

find 2 [(1,3), (5,4), (2,3), (1,1)]

    Saída:

    
3
  • Porém essa forma de criar novos tipos não permite criação de tipos mais complexos, como tipos recursivos: 
    type BinTree a = (BinTree a, a, BinTree a)

2 Tipos de Dados Algébricos

  • Tipos completamente novos.
  • Pode conter tipos primitivos.
  • Permite expressividade.
  • Permite checagem em tempo de compilação

2.1 Tipos Soma

Tipo soma:

data Bool = True | False
  • data: declara que é um novo tipo
  • Bool: nome do tipo
  • True | False: poder assumir ou True ou False

Vamos criar um tipo que define a direção que quero andar:

data Dir = Norte | Sul | Leste | Oeste

Com isso podemos criar a função para:

type Coord = (Int, Int)
type Passo = Coord -> Coord

data Dir = Norte | Sul | Leste | Oeste

para :: Dir -> Passo
para Norte (x,y) = (x, y + 1)
para Sul   (x,y) = (x, y - 1)
para Leste (x,y) = (x + 1, y)
para Oeste (x,y) = (x - 1, y)

E a função caminhar:

type Coord = (Int, Int)
type Passo = Coord -> Coord

data Dir = Norte | Sul | Leste | Oeste

caminhar :: [Dir] -> Passo
caminhar []     coord = coord
caminhar (d:ds) coord = caminhar ds (para d coord)

2.2 Tipos Produto

  • Tipo produto:
data Ponto = MkPonto Double Double
  • data: declara que é um novo tipo
  • Ponto: nome do tipo
  • MkPonto: construtor (ou envelope) - declaração implícita de uma função usada para criar um valor do tipo Ponto
  • Double Double: tipos que ele encapsula

O nome do tipo e o nome do construtor podem ser (e tipicamente são) os mesmos! Apesar de PODEREM ser os mesmos nomes, vivem em espaços de nomes diferentes e NÃO são a mesma coisa.

Para ser possível imprimir esse tipo:

data Ponto = MkPonto Double Double
		      deriving (Show)

  • deriving: derivado de outra classe

  • Show: tipo imprimível

  • Isso faz com que o Haskell crie automaticamente uma instância da função show para esse tipo de dado.

  • Para usá-lo em uma função devemos sempre envelopar a variável com o construtor.
dist :: Ponto -> Ponto -> Double
dist (MkPonto x y) (MkPonto x' y') = sqrt $ (x-x')^2 + (y-y')^2

dist (MkPonto 1 2) (MkPonto 1 1)

Saída:


1.0
  • Podemos misturar os tipos soma e produto:
data Forma = Circulo Ponto Double
	   | Retangulo Ponto Double Double

-- um quadrado é um retângulo com os dois lados iguais
quadrado :: Ponto -> Double -> Forma
quadrado p n = Retangulo p n n
  • Circulo e Retangulo são funções construtoras:
> :t Circulo
Circulo :: Ponto -> Double -> Forma

> :t Retangulo
Retangulo :: Ponto -> Double -> Double -> Forma
  • As declarações de tipos também podem ser parametrizados, considere o tipo Maybe:
data Maybe a = Nothing | Just a
  • A declaração indica que um tipo Maybe a pode não ser nada ou pode ser apenas o valor de um tipo a.
  • Esse tipo pode ser utilizado para ter um melhor controle sobre erros e exceções:
-- talvez a divisão retorne um Int
maybeDiv :: Int -> Int -> Maybe Int
maybeDiv _ 0 = Nothing
maybeDiv m n = Just (m `div` n)

maybeHead :: [a] -> Maybe a
maybeHead [] = Nothing
maybeHead xs = Just (head xs)
  • Eses erros podem ser capturados com a expressão case:
divComErro :: Int -> Int -> Int
divComErro m n = case (maybeDiv m n) of
		     Nothing -> error "divisão por 0"
		     Just x  -> x
  • A expressão case nos permite fazer pattern matching dentro do código da função com quaisquer expressões e não apenas nos seus parâmetros
  • Um outro tipo interessante é o Either definido como:
data Either a b = Left a | Right b
  • Esse tipo permite que uma função retorne dois tipos diferentes, dependendo da situação.
-- ou retorna uma String ou um Int
eitherDiv' :: Int -> Int -> Either String Int
eitherDiv' _ 0 = Left "divisao por 0"
eitherDiv' m n = Right (m `div` n)

print $ eitherDiv' 2 2
print $ eitherDiv' 2 0

Saída:


Right 1
Left "divisao por 0"
()

2.3 Exercício 1

  • Crie um tipo Fuzzy que pode ter os valores Verdadeiro; Falso; ou Pertinencia Double que define um intermediário entre Verdadeiro e Falso.

  • Crie uma função fuzzifica que recebe um Double e retorna Falso caso o valor seja menor ou igual a 0, Verdadeiro se for maior ou igual a 1 e Pertinencia v caso contrário.

2.4 Exercício 1 - Resposta

data Fuzzy = Falso | Pertinencia Double | Verdadeiro

fuzzifica :: Double -> Fuzzy
fuzzifica x | x <= 0    = Falso
	    | x >= 1    = Verdadeiro
	    | otherwise = Pertinencia x

2.5 Newtype

  • Uma terceira forma de criar um novo tipo é com a função newtype, que permite apenas um construtor:
newtype Nat = N Int

  • A diferença entre newtype e type é que o primeiro define um novo tipo enquanto o segundo é um sinônimo.

  • A diferença entre newtype e data é que o primeiro define um novo tipo até ser compilado, depois ele é substituído como um sinônimo. Isso ajuda a garantir a checagem de tipo em tempo de compilação.

3 Tipos Recursivos

  • Um exemplo de tipo recursivo é a árvore binária, que pode ser definida como:
data Tree a = Leaf a | Node (Tree a) a (Tree a)
  • Ou seja, ou é um nó folha contendo um valor do tipo a, ou é um nó contendo uma árvore à esquerda, um valor do tipo a no meio e uma árvore à direita.
  • Desenhe a seguinte árvore:
t :: Tree Int
t = Node (Node (Leaf 1) 3 (Leaf 4)) 5
       (Node (Leaf 6) 7 (Leaf 9))

Podemos definir uma função contem que indica se um elemento x está contidado em uma árvore t:

contem :: Eq a => Tree a -> a -> Bool
contem (Leaf y) x     = x == y
contem (Node l y r) x = x == y || l `contem` x
			       || r `contem` x

print $ t `contem` 5
print $ t `contem` 0

Saída:


True
False
()

3.1 Exercício 2

  • Altere a função contem levando em conta que essa é uma árvore de busca, ou seja, os nós da esquerda são menores ao nó atual, e os nós da direita são maiores.

3.2 Exercício 2 - Resposta

contem :: Ord a => Tree a -> a -> Bool
contem (Leaf y) x                 = x == y
contem (Node l y r) x | x == y    = True
		      | x < y     = l `contem` x
		      | otherwise = r `contem` x

3.3 Record Type

  • Uma outra forma de definir um tipo produto Haskell

é com a sintaxe Record Type :

data Ponto3D = Ponto { coordX :: Double
		     , coordY :: Double
		     , coordZ :: Double
		     }

Essa sintaxe cria automaticamente as funções coordX, coordY, coordZ que retornam o valor daquele campo do seu tipo.

4 Álgebra dos Tipos

  • Os Tipos de Dados Algébricos apresentam algumas similaridades com a Álgebra matemática.
  • Efetivamente, as definições de Tipo Soma e Tipo Produto remetem a essas operações algébricas.
  • Vamos construir elementos de álgebra utilizando ADTs: 
    data Zero
data Um = ()
  • O tipo Zero é um tipo que não contém valor algum!
  • O tipo Um é um tipo contendo apenas um único valor! 
    data Zero
data Um = ()
  • Notem que não temos como criar uma função que recebe um valor do tipo Zero, pois não temos como passar algo que não existe: 
    data Zero

absurdo :: Zero -> a
absurdo ?? = ??
  • Já uma função que recebe um valor do tipo Um e retorna um valor de um tipo específico, é equivalente a declarar uma variável contendo tal valor: 
    data Um = ()

inteiro :: Um -> Int
inteiro () = 10

var_inteiro :: Int
var_inteiro = 10
  • Da mesma forma podemos criar uma função a -> Um que recebe um valor de qualquer tipo, porém não traz informação alguma: 
    data Um = ()

fim :: a -> ()
fim x = ()
  • Os tipos Zero e Um são definidos no Haskell como Void e () (chamado unit ).
  • O tipo Either é representante da soma de tipos, e o tipo Pair representa a operação de produto: 
    data Either a b = Left a | Right b
data Pair   a b = (a, b)
  • O tipo Either Void () pode ser lido como a soma de \(0\) e \(1\): 
    type ZeroMaisUm = Either Void ()
    Quantos valores possíveis existem no tipo ZeroMaisUm?
  • Esse tipo contém \(0 + 1 = 1\) valores possíveis! 
    type ZeroMaisUm = Either Void ()
  • Vamos analisar o tipo Bool: 
    data Bool = False | True
  • Ele é simplesmente a soma de dois valores unitários! 
    data Bool  = False | True
type Bool' = Either () ()
  • Podemos provar isso criando funções que transformam qualquer Bool em Bool' e vice-versa: 
    data Bool  = False | True
type Bool' = Either () ()

bool2bool' False = Left  ()
bool2bool' False = Right ()

bool'2bool (Left ()) = False
bool'2bool (Right ()) = True

O tipo Either define a soma de dois tipos ou a união disjunta do conjunto definido por dois tipos.

  • Qualquer tipo soma pode ser definido por encadeamento de Either: 
    data Dir  = Norte | Sul | Leste | Oeste
data Dir' = Either (Either ()) (Either ())

norte, sul, leste, oeste :: Dir'
norte = Left (Left ())
sul   = Left (Right ())
leste = Right (Left ())
oeste = Right (Right ())
  • Supondo que o tipo Char possui \(256\) caracteres quantos valores possui o tipo Cod_Prod? 
    data Cod_Prod = Either Char Char

Resposta:

  • \(256 + 256 = 512\) valores distintos! 
    data Cod_Prod = Either Char Char
  • Trabalhando com o tipo Pair, vamos definir o produto de Void e (): 
    data ZeroVezesUm = Pair Void ()
    Quantos valores existem para esse tipo?

Resposta:

  • Eu não posso criar um valor para esse tipo, pois isso implica em ter que atribuir um valor para o campo do tipo Void: 
    data ZeroVezesUm = Pair Void ()
    Portanto esse tipo possui \(0 \times 1 = 0\) valores possíveis.
  • Da mesma forma o tipo: 
    data UmVezesUm = Pair () ()
    possui somente \(1 \times 1 = 1\) valor que é Pair () ().
  • Todo tipo produto pode ser construído genericamente como um Pair: 
    data Pontos3D  = P Double Double Double
type Pontos3D' = Pair Double (Pair Double Double)

p2p' (P x y z)           = Pair x (Pair y z)
p'2p (Pair x (Pair y z)) = P x y z
  • Supondo que o tipo Char possui \(256\) caracteres quantos valores possui o tipo Valida_Cod? 
    data Valida_Cod = Pair Char Bool

Resposta:

  • \(256 \times 2 = 512\) valores distintos!
data Valida_Cod = Pair Char Bool
  • Esses dois tipos possuem \(512\) valores, eles são equivalentes? 
    data Cod_Prod   = Either Char Char
data Valida_Cod = Pair Char Bool
    Na Álgebra podemos dizer que \(2 \times x = x + x\), então…
data Cod_Prod   = Either Char Char
data Valida_Cod = Pair Char Bool

prod2valida (Left c)  = Pair c False
prod2valida (Right c) = Pair c True

valida2prod (Pair c False) = Left c
valida2prod (Pair c True)  = Right c
  • Será que \((x + y) \times z = (x \times z) + (y \times z)\)?
data Tipo1 x y z = Pair (Either x y) z
data Tipo2 x y z = Either (Pair x z) (Pair y z)

t1t2 (Pair (Left x) z)  = Left (Pair x z)
t1t2 (Pair (Right y) z) = Right (Pair y z)

t2t1 (Left (Pair x z))  = (Pair (Left x) z)
t2t1 (Right (Pair y z)) = (Pair (Right y) z)
  • Uma vez que as propriedades algébricas funcionam com os ADTs, podemos reestruturar nossos tipos para formas equivalentes quando essas forem mais fáceis de trabalhar.
  • Uma função caracteriza um tipo exponencial:
f :: a -> b -- b^a
  • Ou seja, uma função Bool -> a possui \(a^2\) combinações possíveis de entrada e saída. Por exemplo, quantas definições existem para Bool -> Bool?
id :: Bool -> Bool
id False = False
id True  = True

allFalse :: Bool -> Bool
allFalse False = False
allFalse True  = False

allTrue :: Bool -> Bool
allTrue False = True
allTrue True  = True

not :: Bool -> Bool
not False = True
not True  = False

O tipo da função restringe as possíveis implementações dela, com isso alguns erros de implementação podem ser verificados em tempo de compilação.

Se a função contém tipos paramétricos, ela se torna ainda mais restrita!

5 Zippers

  • Além das operações de adição, multiplicação e exponenciação, o que mais podemos fazer com nossos tipos?
  • Considere o tipo lista:
data List a = Empty | Cons a (List a)
  • Transformando isso em uma notação algébrica, denotando List a como \(L(a)\), Empty como \(1\), temos \(L(a) = 1 + a \cdot L(a)\).
data List a = Empty | Cons a (List a)
  • Rearranjando temos que:

\begin{align} L(a) &= 1 + a \cdot L(a) \\ L(a) - a \cdot L(a) &= 1 \\ (1 - a) \cdot L(a) &= 1 \\ L(a) &= \frac{1}{1 - a} \end{align}

  • A Série de Taylor da expressão \(\frac{1}{1 - a}\) é \(1 + a + a^2 + a^3 + \ldots\) que representa o fato de que uma lista guarda informação de \(0\) elementos (Empty), ou de \(1\) elemento, ou \(2\), ou \(3\), etc.
  • Dada uma lista de \(n\) elementos, eu gostaria de criar um ponto de foco em determinado elemento dessa lista assim como poder caminhar livremente para frente ou para trás.
  • Em Cálculo, a derivida de uma função \(f(x)\) em um certo ponto \(x_0\) nos dá uma visão das propriedades da função naquele local. Ou seja, um foco da função naquele ponto.

Será que podemos derivar um ADT? 🤔

  • Derivando o nosso tipo lista \(L(a) = \frac{1}{1 - a}\) temos:

\begin{equation*} L’(a) = \frac{1}{(1 - a)^2} = \frac{1}{1 - a} \times \frac{1}{1 - a} \end{equation*}

  • Ou seja, a derivada de nossa lista são…DUAS listas! 
    type DiffList a = Pair (List a) (List a)
  • Esse tipo de estrutura é conhecida como Zipper e traz diversos benefícios para o uso de estruturas atravessáveis : 
    data Zipper a = Z [a] [a]

toZipper :: [a] -> Zipper a
toZipper xs = Z [] xs

fromZipper :: Zipper a -> [a]
fromZipper (Z lft rgt) = reverse lft ++ rgt

data Zipper a = Z [a] [a]

focus :: Zipper a -> a
focus (Z _ []) = error "Lista vazia!"
focus (Z _ (x:xs)) = x

walkRight, walkLeft :: Zipper a -> Zipper a
walkRight (Z lft (x:rgt)) = Z (x:lft) rgt
walkLeft  (Z (x:lft) rgt) = Z lft (x:rgt)
  • Agora temos uma forma de caminhar para frente e para trás na lista em tempo constante!
  • Podemos fazer o mesmo com uma árvore binária? 
    data Tree a = Leaf | Node { left  :: Tree a
			  , node  :: a
			  , right :: Tree a
			  }
  • Algebricamente definimos essa árvore como \(T(a) = 1 + a \cdot T(a)^2\). A derivada dessa função é:

\begin{align*} T’(a) &= T(a)^2 + 2 \cdot a \cdot T(a) \cdot T’(a) \\ T’(a) &= T(a)^2 \cdot \frac{1}{1 - 2\cdot a \cdot T(a)} \\ \end{align*}

  • A expressão \(T(a)^2 \cdot \frac{1}{1 - 2\cdot a \cdot T(a)}\) pode ser traduzida em uma ADT como: 
    data From     = Lft | Rgt
data Zipper a = Zipper { left  :: Tree a
		       , right :: Tree a
		       , focus :: [(From, a, Tree a)]
		       }
    O foco atual é composto pelo elemento-foco, a direção de onde ele veio e a árvore acima desse foco.

  • Olhando para essa definição, vamos analisar as possíveis configurações com diferentes quantidade de árvores:

    \(1 + 2^0T^1 + 2^1T^2 + 2^2T^3 + \ldots\)

    que é a série:

    \(\sum_{i=1}{2^{i-1}T^i} = \frac{T}{1 - 2T}\)

  • Isso aqui gera a seguinte estrutura simplificada:
data Zipper a = Zipper { focus :: Tree a
		       , histo :: [Either (Tree a) (Tree a)]
		       } deriving Show
  • Converter uma árvore em um Zipper basta colocar os ramos da esquerda e da direita em seus respectivos campos e criar uma lista contendo o nó raiz (os outros elementos da tupla não importam). 
    toZipper :: Tree a -> Zipper a
toZipper Leaf = Zipper Leaf []
toZipper n    = Zipper n []
  • A conversão de um Zipper para um Tree requer que estejamos com o foco na raíz. Para isso, basta caminharmos para cima até chegar a um único elemento na lista de focos. 
    fromZipper :: Zipper a -> Tree a
fromZipper tz =
  case histo tz of
    []          -> focus tz
    _           -> fromZipper (goUp tz)
  • Andar para esquerda (direita) basta observar o foco atual e colocar o filho esquerdo (direito) como novo foco, adicionando o foco atual sem esse filho no histórico. 
    goLeft :: Zipper a -> Zipper a
goLeft tz =
  case focus tz of
    Node Leaf _ _ -> tz
    Node l x r    -> Zipper l (Left (Node Leaf x r) : histo tz)

goRight :: Zipper a -> Zipper a
goRight tz =
  case focus tz of
    Node _ _ Leaf -> tz
    Node l x r    -> Zipper r (Right (Node l x Leaf) : histo tz)

  • Para andar para cima basta recuperarmos a informação do primeiro elemento da lista de históricos.

    goUp :: Zipper a -> Zipper a
goUp (Zipper f [])     = Zipper f []
goUp (Zipper f (h:hs)) =
  case h of
    Left  (Node _ x r) -> Zipper (Node f x r) hs
    Right (Node l x _) -> Zipper (Node l x f) hs

    Código no Repl.it

6 Classes de Tipo

  • Aprendemos em uma aula anterior sobre as classes de tipo, classes que definem grupos de tipos que devem conter algumas funções especificadas.

  • Para criar uma nova classe de tipos utilizamos a palavra reservada class:

class Eq a where
   (==), (/=) :: a -> a -> Bool

   x /= y = not (x == y)
  • Essa declaração diz: para um tipo a pertencer a classe Eq deve ter uma implementação das funções (==) e (/=).
class Eq a where
   (==), (/=) :: a -> a -> Bool

   x /= y = not (x == y)
  • Além disso, ela já fornece uma definição padrão da função (/=), então basta definir (==).
class Eq a where
   (==), (/=) :: a -> a -> Bool

   x /= y = not (x == y)

6.1 Instâncias da Classe

  • Para definirmos uma nova instância de uma classe basta declarar:
instance Eq Bool where
   False == False = True
   True  == True  = True
   _     == _     = False
  • Apenas tipos definidos por data e newtype podem ser instâncias de alguma classe.
  • Uma classe pode estender outra para forma uma nova classe. Considere a classe Ord:
class Eq a => Ord a where
   (<), (<=), (>), (>=) :: a -> a -> Bool
   min, max             :: a -> a -> a

   min x y | x <= y    = x
	   | otherwise = y

   max x y | x <= y    = y
	   | otherwise = x
  • Ou seja, antes de ser uma instância de Ord, o tipo deve ser também instância de Eq.

Tire da cabeça os conceitos de Classe e Instância vindos de orientação a objetos. Aqui uma classe de tipos nada mais é que um conjunto, uma coleção, uma lista de tipos. Por sua vez, uma instância nada mais é que dizer que um tipo pertence a uma classe, ou seja, está dentro daquele conjunto de classes.

Seguindo nosso exemplo de Booleano, temos:

instance Ord Bool where
    False < True = True
    _     < _    = False

    b <= c = (b < c) || (b == c)
    b > c  = c < b
    b >= c = c <= b

Lembrando:

  • Tipo: coleção de valores relacionados.
  • Classe: coleção de tipos que dão suporte a certas funções ou operadores.
  • Métodos: funções requisitos de uma classe.
  • Instância: um tipo que pertence a uma determinada classe

6.2 Eq - classe da igualdade

Tipos que podem ser comparados em igualdade e desigualdade:

(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool

1 == 2

Saída:


False
[1,2,3] == [1,2,3]

Saída:


True
"Ola" /= "Alo"

Saída:


True

6.3 Ord - classe de ordem

A classe Eq acrescido de operadores de ordem:

(<) :: a -> a -> Bool
(<=) :: a -> a -> Bool
(>) :: a -> a -> Bool
(>=) :: a -> a -> Bool
min :: a -> a -> a
max :: a -> a -> a

4 < 6

Saída:


True
min 5 0

Saída:


0
max 'c' 'h'

Saída:


'h'
"Ola" <= "Olaf"

Saída:


True

6.4 Show - classe imprimíveis

A classe Show define como imprimir um valor de um tipo:

show :: a -> String

show 10.0

Saída:


10.0
show [1,2,3,4]

Saída:


[1,2,3,4]

6.5 Read - classe legíveis

A classe Read define como ler um valor de uma String:

read :: String -> a

Precisamos especificar o tipo que queremos extrair da String:

read "12.5" :: Double

Saída:


12.5
read "False" :: Bool

Saída:


False
read "[1,3,4]" :: [Int]

Saída:


[1,3,4]

6.6 Num - classe numérica

A classe Num define todos os tipos numéricos:

(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a

1 + 3

Saída:


4
6 - 9

Saída:


-3
3 * (-2)

Saída:


-6

Valores negativos devem ser escritos entre parênteses para remover ambiguidades com o operador de subtração.

6.7 Integral - classe de números inteiros

A classe Integral define todos os tipos numéricos inteiros:

quot :: a -> a -> a
rem :: a -> a -> a
div :: a -> a -> a
mod :: a -> a -> a
quotRem :: a -> a -> (a, a)
divMod :: a -> a -> (a, a)
toInteger :: a -> Integer

10 `quot` 3

Saída:


3
10 `rem` 3

Saída:


1
10 `div` 3

Saída:


3
10 `mod` 3

Saída:


1

As funções quot e rem arredondam para o \(0\), enquanto div e mod para \(-\infty\).

6.8 Fractional - classe de números racionais

  • A classe Fractional define todos os tipos numéricos fracionários
(/) :: a -> a -> a
recip :: a -> a

10 / 3

Saída:


3.3333333333333335
recip 10

Saída:


0.1

Qual a diferença entre esses dois operadores de exponenciação?

(^) :: (Num a, Integral b) => a -> b -> a
(**) :: Floating a => a -> a -> a

6.9 Floating - classe de números de ponto flutuante

class Fractional a => Floating a where
  pi :: a
  exp :: a -> a
  log :: a -> a
  sqrt :: a -> a
  (**) :: a -> a -> a
  logBase :: a -> a -> a

sin :: a -> a
cos :: a -> a
tan :: a -> a
asin :: a -> a
acos :: a -> a
atan :: a -> a
sinh :: a -> a
cosh :: a -> a
tanh :: a -> a
asinh :: a -> a
acosh :: a -> a
atanh :: a -> a

6.10 Info

  • No ghci, o comando :info mostra informações sobre os tipos e as classes de tipo:
> :info Integral
class (Real a, Enum a) => Integral a where
  quot :: a -> a -> a
  rem :: a -> a -> a
  div :: a -> a -> a
  mod :: a -> a -> a
  quotRem :: a -> a -> (a, a)
  divMod :: a -> a -> (a, a)
  toInteger :: a -> Integer
  {-# MINIMAL quotRem, toInteger #-}
  • No ghci, o comando :info mostra informações sobre os tipos e as classes de tipo:
> :info Bool
data Bool = False | True    -- Defined in ‘GHC.Types’
instance Eq Bool -- Defined in ‘GHC.Classes’
instance Ord Bool -- Defined in ‘GHC.Classes’
instance Show Bool -- Defined in ‘GHC.Show’
instance Read Bool -- Defined in ‘GHC.Read’
instance Enum Bool -- Defined in ‘GHC.Enum’
instance Bounded Bool -- Defined in ‘GHC.Enum’

6.11 Derivação de instâncias

  • Em muitos casos o Haskell consegue inferir as instâncias das classes mais comuns, nesses casos basta utilizar a palavra-chave deriving ao definir um novo tipo:
data Bool = False | True
	    deriving (Eq, Ord, Show, Read)

6.12 Classe Enum

  • Implementa as funções:
succ, pred, toEnum, fromEnum

data Dias = Dom | Seg | Ter | Qua | Qui | Sex | Sab
		   deriving (Show, Enum)

Enum é enumerativo:

succ Seg == Ter
pred Ter  == Seg
fromEnum Seg == 0
toEnum 1 :: Dias == Ter
-- E pode-se fazer
[Seg .. Sex] == [Seg, Ter, Qua, Qui, Sex]

6.13 Exercício 3

  • Defina um tipo para jogar o jogo Pedra, Papel e Tesoura e defina as funções ganhaDe, perdeDe.

  • Defina também uma função denominada ganhadores que recebe uma lista de jogadas e retorna uma lista dos índices das jogadas vencedoras.

6.14 Exercício 3 - Resposta

data Jogada = Pedra | Papel | Tesoura
	      deriving (Show, Enum, Eq)

ganhaDe :: Jogada -> Jogada -> Bool
Pedra   `ganhaDe` Tesoura = True
Papel   `ganhaDe` Pedra   = True
Tesoura `ganhaDe` Papel   = True
j1      `ganhaDe` j2      | j1 == j2  = True
			  | otherwise = False

data Jogada = Pedra | Papel | Tesoura
	      deriving (Show, Enum, Eq)

perdeDe :: Jogada -> Jogada -> Bool
j1 `perdeDe` j2 = not $ j1 `ganhaDe` j2

6.15 Para saber mais…

7 Construtores de Tipos

  • Em aulas anteriores vimos o conceito de construtores de tipos, quando criamos novos tipos. Eles recebem um tipo como parâmetro e criam um novo tipo:
listaDeDouble :: [Double]
talvezInt     :: Maybe Int
arvoreChar    :: Tree Char
  • Tipo paramétrico é todo tipo que possui um parâmetro de tipo:
[a], Maybe a, Tree a, ...
  • Considere as seguintes funções:
dobra :: Int  -> Int
dobra x = 2*x

flip :: Coin -> Coin
flip Cara  = Coroa
flip Coroa = Cara
  • Se quisermos aplicar essas funções para uma lista desses tipos, basta:
dobraLista :: [Int]  -> [Int]
dobraLista = map (*2)

flipLista :: [Coin] -> [Coin]
flipLista = map flip
  • E se quisermos aplicar essa função para um Maybe Coin, ou Tree Int?
dobraArvore :: Tree Int -> Tree Int
dobraArvore = ??

flipMaybe :: Maybe Coin -> Maybe Coin
flipMaybe = ??

8 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.