TROCOU O LINK PARA O LIVRO TEXTO

livro texto capitulos: 2 (tuplas, range, list comprehension) , 4 (where, let, case) e 5 (recursão)

haskell online

Sintaxe

Precedencia

a b c d + g h i

• funçoes tem maior prioridade (gruda antes) que operadores (prioridade 10)

• operadores tem prioridades de 9 a 1 https://www.haskell.org/onlinereport/decls.html#fixity

• isso é a soma de a b c d com g h i que em sintaxe tradicional de linguagens de programação é a(b,c,d) e g(h,i)

Blocos

• indenta com brancos

• (acho) que dentro do bloco precisa esta alinhado

• os diferentes blocos nao precisam estar alinhados entre si (como no Python)

maior a b = if a>b 
              then a 
              else b 

Guards

maior a b = if a > b 
       then a
       else b

maior' a b 
 | a > b = a
 | otherwise = b

Da notação matemática, mas com a condição antes do valor

f(a,b)=\left\{ \begin{array}{l l} a, & {if}\ a>b \\ b, & {otherwise} \end{array}\right.

Variáveis e funções locais

• posição do item na lista (0 se nao esta la, 1 se é o primeiro)

posicao it [] = 0
posicao it (x:xs) 
  | it == x = 1
  | otherwise = if (posicao it xs) == 0 then 0 else (posicao it xs) + 1  
  --- dupla recursao a nao ser que (posicao it xs) == 0

where - define as variáveis (e funções) locais depois da chamada “principal”

maior [x] = x
maior (x:xs) = if x>mm then x else mm
    where mm = maior xs

let … in - define as variáveis e funções locais antes da chamada principal

maior [x] = x
maior (x:xs) = let
         mm = maior xs
     in if x>mm then x else mm 

where permite continuar usando guards

maior [x] = x
maior (x:xs) 
   | x>mm = x
   | otherwise = mm
   where mm = maior xs

Recursão com acumulador

As funções recursivas até agora são do tipo - recursao no resto da lista e depois computa a solução com a cabeça da lista

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

A ideia do acumulador é fazer o calculo usando o head e o acumulador recebido e passar o acumulador alterado para a recursão.

O acumulador acumula o trabalho das instancias que vieram antes da recursão

--  soma' l acc
soma' [] acc = acc   -- caso base sempre retorna o acumulador
soma' (x:xs) acc = soma' xs (acc+x) 
-- caso recursivo faz primeiro a conta (acc+x) e so no final chama a recursao

Mas a primeira chamada funçao soma' precisa setar o acumulador da forma certa. A funçao soma' é uma função local de soma

soma l = soma' l 0
  where soma' [] acc = acc
        soma' (x:xs) acc = soma' xs (x+acc)

caso do reverte

• reverte uma lista

reverte [] = []
reverte (x:xs) = (reverte xs) ++ [x]

Esse codigo é quadratico pois o ++ passeia pela primeira lista “até achar o final” para grudar a segunda lista (se a lista é implementada como uma lista ligada)

• segundo a resposta em https://stackoverflow.com/questions/2688986/how-are-lists-implemented-in-haskell-ghc no Haskell listas são implementadas como lista ligadas)

• em python listas são implementadas como dynamic array veja: https://medium.com/analytics-vidhya/how-lists-are-implemented-in-python-9b055fbc8d36

T(n) = T(n-1)+n+c
==> T(n) = O(n^2)

neste caso, recursão com acumulador torna a função linear

reverte l = reverte' l []
   where 
     reverte' [] acc = acc
     reverte' (x:xs) acc = reverte' xs (x:acc)

List Comprehension

[ f x | x <- fonte, condicao1, condicao2]

[ x+10 | x <- [1..10], x `mod` 2 == 0]

[1..10] é um range - gera uma lista de 1 a 10

[2,5..30] gera a lista [2,5,8,11,14,17,20,23,26,29]

somapares xs = soma [x | x <- xs, x `mod` 2 == 0]

Tupla

Como a tupla do Python. Mas funcoes de listas nao funcionam em tuplas

head ("Jose" , 47)

Pattern matching funciona em tuplas

somaAno (n,id) = (n, id+1)

Para tuplas de 2 elementos:

fst ("jose",3)
==> "jose"

fst (a,b) = a

snd ("jose",3)
==> 3

snd (a,b) = b

Retornar uma tupla é o jeito para uma função retornar mais de uma coisa

trocaultimo

• troca a ultima vez na lista que aparece o valor velho pelo valor novo - apenas na ultima vez que velho aparece

trocaultimo velho novo lista = fst (trocaultimo' velho novo lista)

trocaultimo' velho novo []  = ([],False)
trocaultimo' velho novo (x:xs) = let
             (xxs,trocou) = trocaultimo' velho novo xs
          in if trocou || (x /= velho)  then (x:xxs, trocou)
                                        else (novo:xxs, True)

trocaultimo retorna uma tupla com a lista trocada e um booleano se ele trocou ou nao o velho pelo novo.

Mais simples:

trocaultimo n v l = reverte (troca1 n v (reverte l))

Exercícios

refaça os exercicios da aula passada usando variaveis locais, recursão com acumulador, list comprehension, funções retornando tuplas, combinando funções ja implementadas, etc se for o caso. Em particular tente usar acumuladores para aprender a pensar dessa forma.

Alem disso faça:

• posicoes - dado um item e uma lista, retorna uma lista com todas as posicoes (primeiro elemento esta na posição 1) do item na lista

• split - dado um item e uma lista retorna uma lista de listas, todos os elementos da lista antes do item (a primeira vez que ele aparece) e todos depois

split "qwertyuiopoiuyt" 't' ==> ["qwer", "yuiopoiuyt"]

• splitall - mesma coisa que o split mas retorna todas as sublistas

splitall "qwertyuiopoiuytxxt" 't' ==> ["qwer", "yuiopoiuy", "xx", ""]  ou  ["qwer", "yuiopoiuy", "xx"]

• drop n lista - a lista sem os n primeiros elementos - essa função já esta implementada no Prelude

• take n lista - os primeiros n elementos da lista - essa função já esta implementada no Prelude