Aula 3

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

haskell online

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

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 em alguns casos
maior [x] = x
maior (x:xs) = if x>(maior xs) then x else (maior xs)  -- dupla recursao

Esses dois códigos sao exponenciais (em alguns casos) no tamanho da lista quando obviamente eles podem ser lineares

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

Nos dois casos precisamos armazenar os valores posicao it xs e maior xs para usa-los em mais de um lugar

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)

Recursão com acumulador podem fazer a otimizacao de ultima chamada ou otimização de cauda (tail call optimization ou last call optimization) - torna o código recursivo tão rápido como um código iterativo. https://medium.com/trainingcenter/o-que-%C3%A9-recurs%C3%A3o-e-tail-call-optimization-tco-f1938188223c

caso do reverte

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

Esse codigo é quadratico pois o ++ passeia pela primeira lista “ate 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)

outras soluções para o maior

maior1 (x:xs) = maior' xs x
  where maior' [] a = a
        maior' (y:ys) a 
           | y>a = maior' ys y
           | otherwise = maior' ys a

maior2 [x] = x
maior2 (x:xs) = max' x (maior2 xs)
  where max' a b 
        | a > b = a
        | otherwise = b

Tupla

“quase-lista” de elementos de tipos diferentes. Mas as funções de lista NÃO funcionam para tuplas

("Jose",47, [4,5])

mas pattern matching funciona em tuplas

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

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

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))

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]

Exercícios

refaça os exercicios da aula passada usando variaveis locias, recursao 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:

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