livro texto (cap 7)

Haskell online

compilado

Faltou em funções de alto nivel

f (g (h x)))

f $ g $ h x

(f . g . h) x

. é a composição de 2 funcoes

normalmente usado em map

map (f . g) lista

map (\x -> f (g x)) lista

da aula passada

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

insereabb :: Ord a => a -> Tree a -> Tree a

insereabb x Vazia = No x Vazia Vazia
insereabb x (No y ae ad)
    | x==y = No y ae ad
    | x<y  = No y (insereabb x ae) ad
    | x>y  = No y ae (insereabb x ad)
    
listatoabb :: Ord a => [a] -> Tree a

listatoabb lst = foldl (flip insereabb) Vazia lst

Modulos

import Data.List  -- tudo !!!

import Data.List (nub,sort)  -- apenas

import qualified Data.List as DL -- qualificado

DL.sort

base packages

https://hackage.haskell.org/package/base

Data.List

De uma olhada em Data.List

• fold, map, filter, elem, etc

• sum, maximum

• !! - acesso a um elemento (indexado apartir do 0)

• zip, zipWith

• lines - divide um stringão em linhas

• words - divide um string em palavras (igual ao split() do python)

• unlines e unwords - inverso das funcoes acima

• sort

• nub - remove duplicadas, partition

• sortBy deleteBy groupBy nubBy

• operações em conjuntos: union, // (set difference) etc

Data.Map.Strict

containers: https://hackage.haskell.org/package/containers

intro https://haskell-containers.readthedocs.io/en/latest/

https://haskell-containers.readthedocs.io/en/latest/map.html

dicionários (implementados como arvores binarias balanceadas, e tempo de acesso = O(log n)

Data.Map.Strict

• empty - dicionario vazio

• fromList :: Ord k => [(k, a)] -> Map k a lista de duplas para um dicionário

• fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a o primeiro argumento é uma função que combina 2 valores que tiverem a mesma chave

• insert Ord k => k -> a -> Map k a -> Map k a insere num dicionário

• insertWith - função de combinação entre valor velho e novo.

  Insert with a function, combining new value and old value. insertWith f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert the pair (key, f new_value old_value).

• delete Ord k => k -> Map k a -> Map k a

• lookup :: Ord k => k -> Map k a -> Maybe a (a ser discutido na aula que vem)

• member Ord k => k -> Map k a -> Bool Retorna um booleano

• map :: (a -> b) -> Map k a -> Map k b map nos valores

• mapWithKey :: (k -> a -> b) -> Map k a -> Map k b map que recebe a chave e transforma os valores

• elems :: Map k a -> [a]

• keys :: Map k a -> [k]

• foldr e foldl funciona (com valores)

import qualified Data.Map.Strict as Map

insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a

Data.char

https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-Char.html

Exercicos (resposta)

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

removeabb :: Ord a => a -> Tree a -> Tree a

removeabb _ Vazia = Vazia
removeabb x (No y ae ad) 
    | x < y  = No y (removeabb x ae) ad
    | x > y  = No y ae (removeabb x ad)
    | x == y = aux1 x ae ad
    

aux1 x ae ad 
    | ae == Vazia = ad
    | otherwise = No novaraiz (removeabb novaraiz ae) ad
    | 
    where
        novaraiz = omaior ae
    
omaior (No x _ Vazia) = x
omaior (No _ _ ad) = omaior ad

essa é uma solução (deselegante).

• o removeabb cuda dos casos simples
• aux1 cuida do caso complicado (remover uma raiz de uma arvore com os 2 lados

a solucao é deselegante por razoes sintaticas (poderia tudo esta como funções auxiliares) mas principalmente porque vc tem que andar pela arvore a esquerda 2 vezes, para achar o maior e para remove-lo

podemos fazer isso de uma so vez

acha_remove_maior :: Ord a => Tree a -> (a,Tree a)

acha_remove_maior (No x ae Vazia) = (x,ae)
acha_remove_maior (No x ae ad) = (maior, No x ae nova_ad)
    where
        (maior,nova_ad) = acha_removemaior ad

agora aux1 fica

aux1 x ae ad 
    | ae == Vazia = ad
    | otherwise = No nova_raiz ae nova_ad
    where
        (nova_raiz,nova_ad) = acha_removemaior ad

melhor ainda é nao definir aux1 e simplesmente colocar a expressão no linha do x==y

solução final:

removeabb :: Ord a => a -> Tree a -> Tree a

removeabb _ Vazia = Vazia
removeabb x (No y ae ad) 
    | x < y  = No y (removeabb x ae) ad
    | x > y  = No y ae (removeabb x ad)
    | x == y && ae == Vazia = ad
    | otherwise =  No nova_raiz ae nova_ad
    where
        (nova_raiz,nova_ad) = acha_removemaior ad

I/O primeira parte

ainda sem ler ou imprimir

• show x apenas converte x p/ string

• read x :: Int para converter um string x para inteiro

• read x :: Float para converter p/ float

• funções lines para quebrar um string em linhas e words para quebrar uma linha nos brancos

• funçoes unlines e unwords para montar o string final

read "  8  " :: Int

read "  8  " :: Float 

show 9.876