Tipos.hs

{-# LANGUAGE NegativeLiterals #-}

module Tipos where

{-
Questao 1
Semelhante à função somar, defina uma função de multiplicação recursiva para números 
naturais mult :: Nat -> Nat -> Nat. Dica: use a função somar definida no material de aula para os números naturais.
-}

data Nat = Zero | Suc Nat deriving Show


somar :: Nat -> Nat -> Nat
somar Zero n = n
somar (Suc m) n = Suc (somar m n)

multiplicar :: Nat -> Nat -> Nat
multiplicar Zero _ = Zero
multiplicar _ Zero = Zero
multiplicar (Suc n1) n2 = somar (multiplicar n1 n2) n2


{-
Questao 2

O Prelude define o tipo Ordering

data Ordering = LT | EQ | GT

e a função

compare :: Ord a => a -> a -> Ordering

que decide se o primeiro valor recebido como argumento é menor (LT), igual (EQ) ou maior (GT) 
que o segundo argumento. Usando essa função redefina a função 
existe :: Ord a => a -> Arvore a -> Bool para árvores binárias de busca.

-}

data ArvoreBinaria a = Folha1 a | No1 a (ArvoreBinaria a) (ArvoreBinaria a)

existe :: Ord a => a -> ArvoreBinaria a -> Bool
existe v (Folha1 f) = f == v
existe v (No1 n esq dir) = case compare v n of
                                EQ -> True
                                LT -> existe v esq
                                GT -> existe v dir

{-
Questao 3

Considere o seguinte tipo de árvores binárias:

data Arvore a = Folha a | No (Arvore a) (Arvore a)

Digamos que a árvore é balanceada se a quantidade de folhas do lado esquerdo 
e do lado direito de todos os nós são iguais ou sua diferença é no máximo 1, 
e suas folhas são consideradas balanceadas por definição. 

Defina uma função balanceada :: Arvore a -> Bool que decide se uma árvore é 
balanceada ou não. Dica: primeiro defina uma função que conta a quantidade de folhas em uma árvore.
-}

data Arvore a = Folha2 a | No2 (Arvore a) (Arvore a)

tamanho :: Arvore a -> Int
tamanho (Folha2 _) = 1
tamanho (No2 esq dir) = tamanho esq + tamanho dir

balanceada :: Arvore a -> Bool
balanceada (Folha2 _) = True
balanceada (No2 esq dir) = (tamanho esq - tamanho dir) `elem` [-1, 0, 1] && balanceada esq && balanceada dir


{-
Questao 4
Defina a função balancear :: [a] -> Arvore a que converte uma lista não vazia em uma árvore balanceada. 

Dica: primeiro defina uma função que divide uma lista em duas metades cujos tamanhos diferem em no máximo 1.
-}

dividirLista :: [a] -> ([a], [a])
dividirLista l = (take (div (length l) 2) l, drop (div (length l) 2) l)

balancear :: [a] -> Arvore a
balancear [e] = Folha2 e
balancear l = No2 (balancear esq) (balancear dir)
              where
                 (esq, dir) = dividirLista l


{-
Questao 5
Dada a definição

data Expr = Val Int | Add Expr Expr

defina a função de alta ordem

avaliar :: Expr -> Int

tal que avaliar substitui cada construtor Val na expressão pelo valor Int representado pelo construtor, 
e cada construtor Add pela aplicação da função (+).
-}

data Expr = Val Int | Add Expr Expr

avaliar :: Expr -> Int
avaliar (Val i) = i
avaliar (Add e1 e2) = avaliar e1 + avaliar e2

{-
Questao 6

Utilizando a definição

data Expr = Val Int | Op Expr Expr

defina a função de alta ordem

folde :: (Int -> a) -> (a -> a -> a) -> Expr -> a

tal que folde f g substitui cada construtor Val na expressão pela aplicação 
da função f ao valor representado pelo Val, e cada construtor Op pela aplicação 
da função g aos valores resultantes de ambas as expressões codificadas pelo construtor Op.
-}

data Expr2 = Val2 Int | Op2 Expr2 Expr2

folde :: (Int -> a) -> (a -> a -> a) -> Expr2 -> a
folde f _ (Val2 i) = f i
folde f g (Op2 e1 e2) = g (folde f g e1) (folde f g e2)

{-
Questao 7

Usando a função folde, defina a função eval :: Expr -> Int que avalia 
uma expressão para um valor inteiro. Uma forma de enxergar o que a função eval 
deve fazer é refletir sobre a seguinte frase: como eu posso usar a função folde 
de forma que eval avalie a expressão assumindo que Op signifique a soma? Por exemplo, 
se eu executasse eval (Op (Val 1) (Val 4)), assumindo que Op é a soma, ela deveria 
retornar 5. Perceba que Op poderia representar qualquer operação sobre os valores, 
basta que você forneça a operação desejada para a função folde.
-}

eval :: Expr2 -> Int
eval = folde id (+)