Aula 4

[1..1000] não cria uma lista de 1000 elementos, cria um objeto que da um elemento por vez quando recebe o pedido, chamados thunk. A vantagem é que isso nao aloca memoria para 1000 numeros

[7..] é um thunk que gera 7, depois 8, depois 9, etc mas nao aloca memoria para uma lista infinita

tudo em haskell sao thunks, promessas de computacao.

so na hora de print (no repl) é que a promessa é executada. Ha outros contextos que executam os thunks - strict (em oposicao a lazy)

let a = [1..]
take 3 a
let b = drop 5 a
let {double [] = [] ; double (x:xs) = (2*x):(double xs)}
let c = double b
let d = double (take 1 c)
d

data

data Ponto = Ponto Float Float -- x e y de um ponto
data Figura = Circulo Ponto Float | Retangulo Ponto Ponto

area (Circulo _ r) = 2 * 3.14 * r
area (Retangulo (Ponto xa ya) (Ponto xb yb)) = abs ((ya-yb)*(xa-xb))

data Ponto = Ponto Float Float deriving (Eq,Read,Show)

o deriving (Eq,Show,Read) extende trivialmente o == e as funções show e read para que o novo tipo Ponto seja subtipos de Eq, Show e Read

Definição de tipos pode conter variaveis de tipo

data Tree a = Vazia | No a (Tree a) (Tree a) deriving (Eq,Show,Read)

Isso define uma arvore binária de a seja o que for a

soma Vazia = 0
soma (No x ae ad) = soma ae + soma ad + x

distancia (Ponto x y) (Ponto a b) = sqrt (dx**2 + dy**2)
        where  dx = x - a
               dy = y - b

• arvore de busca binaria: o no da raiz é maior que todos nós a esquerda e menor que todos nós a direita, e isso vale recursivamente.
• acha um item buma arvore de busca binaria
• verifica se uma arvore é um abb

data Tree a = Vazia | No a (Tree a) (Tree a) deriving (Eq,Show,Read)

isAbb :: Ord a => Tree a -> Bool  -- nao colocar a resticao de Ord na definicao do tipo!!
isAbb Vazia  = True
isAbb (No _ Vazia Vazia)  = True
isAbb (No x Vazia ad) = isAbb ad && x < menor ad
isAbb (No x ae Vazia) = isAbb ae && x > maior ae
isAbb (No x ae ad) = isAbb ae && isAbb ad && x < menor ad && x > maior ae

maior (No x _ Vazia) = x
maior (No x _ ad) = maior ad

menor (No x Vazia _) = x
menor (No x ae _) = menor ae

• insere um item numa abb
• remove um item de uma abb
• calcula a profundidade maxima de uma abb
• coverte uma abb numa lista em ordem infixa (arvore-esquerda, no, arvore-direita)
• converte uma abb numa lista em ordem prefixa (no, ae, ad)
• converte uma lista em uma abb

converteparaabb :: Ord a => [a] -> Tree a

converteparaabb lista  = converte' lista Vazia
   where converte' [] acc = acc
         converte' (x:xs) acc = converte' xs newacc
                   where newacc = insereabb x acc