Aula 6

Dado a declaração de tipo

data Tree a = Vazia | No a (Tree a) (Tree a)

imlemente uma funçao que dado um lista de dados retorna uma arvore de busca binária dos dados (nao precisa estar balanceada)

inserelista :: (Ord a, Eq a) => [a] -> Tree a

Se voce assumir que existe uma funçao insereArvore que dado uma arvore e um item insere o item na arvore o teste so valerá um ponto

insereArvore :: (Ord a, Eq a) => Tree a ->  a -> Tree a

toda funçao em Haskell é "na verdade" uma funçao de 1 argumento (que pode retornar funçoes)

max 4 5

(max 4) 5

let a = max 4

a 3
a 5
:t a

Veja que nos podemos escrver a funcao a como

a x = max 4 x

a = max 4

essa segunda versão é chamada de pointfree style

Funcoes infixas (+, etc)

(8+)
??? (+8)
f1 = (<5)
:t f1

f2 = (5>)
:t f2

maiuscula = (`elem` ['A'..'Z'])

aplica2 f x = f (f x)
:t aplica2

zipWith' f [] _ = []
zipWith' f _ [] = []
zipWith' f (a:as) (b:bs) = f a b : (zipWith' f as bs)

zipWith' (+) [1..5] [1000..]

flip' f = g  
    where g x y = f y x  

zipWith' (flip' div) [2,2..] [10,8,4,0]

flip e zipWith ja estao definidas

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (a:as) = f a : (map f as)

map (5-) [10,8..0]

filter :: (a -> Bool) -> [a] -> [a]  
filter _ [] = []  
filter p (x:xs)   
    | p x       = x : filter p xs  
    | otherwise = filter p xs  

impar x = x `mod` 2 == 1

filter impar [1,5,4,3,6,7,8]

Cria funcoes sem nomes

filter (\ x -> x `mod` 2 == 1) [1,5,4,3,6,7,8]

zipWith (\a b -> if a>b then a+3 else b-1) [1,2,3,4] [5,4,3,2]

foldr é a recursao tradicional (o resultado vem da esquerda)

soma [] = 0
soma (x:xs) = x + (soma xs)

foldr combina valor-inicial lista
foldr _ init [] = init
foldr f init (x:xs) = f x (foldr f init xs)

soma l = foldr (+) 0 l

soma = foldr (+) 0
 

foldl é a recursao com acumulador, que o resultado vem da esquerda

foldl _ acc [] = acc
foldl f acc (x:xs) = foldl f  (f acc x) xs

• reimplemente os exercicios da aula 1 usando as funcoes de alto nivel

(map, filter, fold)

• uma matrix é implementada como uma lista de linhas (que são listas)

1  2  3
4  5  6 
7  8  9
0  0 -1

[[1,2,3],[4,5,6],[7,8,9],[0,0,-1]]

implemente transposta que transpoe uma matrix

• implemente matmul que dado duas matrizes de formatos apropriados multiplica-as. (*)